Time complexity of Merge Sort in python

Question

I implemented merge-sort in python

import sys

def mergeSort(array):
    if len(array) < 2:
        return array

    middle = len(array) / 2
    left   = mergeSort(array[:middle])
    right  = mergeSort(array[middle:])
    return merge(left, right)

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]: result.append(left.pop(0))
        else: result.append(right.pop(0))

    while left: result.append(left.pop(0))
    while right: result.append(right.pop(0))

    return result

array = map(int, sys.stdin)
print mergeSort(array)

But someone told me that the time complexity of list.pop(0) in python is linear or O(n). In that case the above code won't sort in O(n log n). What changes should I make to it?

See this question: http://stackoverflow.com/questions/7063697/why-is-my-mergesort-so-slow-in-python . Specifically the community wiki/huitseeker answer. It has lots of sorts: https://gist.github.com/1146063 — jon, Mar 08 '12 at 18:13

score 3 · Answer 1 · edited May 23 '17 at 12:10

3

The someone who told you that is correct. list.pop() is O(1), but list.pop(0) is linear, because the whole list has to be shifted to fill in the space. Thus in general, list.pop(x) is O(n - x). As Ignacio suggests, you could use a deque -- popping from a deque is O(1) on either side. (But slows to O(n) in the middle.)

edited May 23 '17 at 12:10

Community

1
1

answered Mar 08 '12 at 17:12

senderle

145,869
36
209
233

score 2 · Answer 2 · answered Mar 08 '12 at 17:10

2

You could use a collections.deque, but you still won't beat Timsort.

answered Mar 08 '12 at 17:10

Ignacio Vazquez-Abrams

776,304
153
1,341
1,358

My aim is not to beat Timsort here. – fR0DDY Mar 08 '12 at 17:13

Time complexity of Merge Sort in python

2 Answers2