CODEWITHSUNDEEP
python
fR0DDY
fR0DDY

Reputation: 805

Time complexity of Merge Sort in python

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?

Upvotes: 2

Views: 2092

Answers (2)

senderle
senderle

Reputation: 150997

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.)

Upvotes: 3

Ignacio Vazquez-Abrams
Ignacio Vazquez-Abrams

Reputation: 798686

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

Upvotes: 2

Related Questions