Issue 10: The Case of the Quadratic Merge Sort

Anyone who has never made a mistake has never tried anything new.
- Albert Einstein  

This week, we were introduced to two efficient sorting algorithm: Quick sort and Merge sort. Both algorithm applies the idea of "divide and conqueror" by splitting a list in half and sorting them recursively. This means that we should expect both algorithm to have an average run time of O(n log n).

However, an interesting issue came up when this code from the 9 AM lecture was ran:

from random import shuffle, randint


def quick(L: list) -> list:
    """Produce a sorted version of L

    >>> quick([2, 1, 3])
    [1, 2, 3]
    """
    if len(L) < 2:
        return L[:]
    else:
        i = randint(0, len(L) - 1)
        return (quick([x for x in L if x < L[i]]) +
                [L[i]] +
                quick([x for x in (L[0:i] + L[i+1:]) if x >= L[i]]))


def merge(L1, L2):
    """return merge of L1 and L2

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([1, 2, 3], [0, 4, 5])
    [0, 1, 2, 3, 4, 5]
    >>> merge([0], [1, 2, 3, 4])
    [0, 1, 2, 3, 4]
    """
    L = []
    i1, i2 = 0, 0
    while L1[i1:] and L2[i2:]:
        if L1[i1] < L2[i2]:
            L.append(L1[i1])
            i1 += 1
        else:
            L.append(L2[i2])
            i2 += 1
    return L + L1[i1:] + L2[i2:]

def merge_sort(L):
    """Produce copy of L in non-decreasing order

    >>> merge_sort([1, 5, 3, 4, 2])
    [1, 2, 3, 4, 5]
    >>> L = list(range(20))
    >>> shuffle(L)
    >>> merge_sort(L) == list(range(20))
    True
    """
    if len(L) < 2 :
        return L[:]
    else :
        return merge(merge_sort(L[:len(L)//2]), merge_sort(L[len(L)//2:]))


if __name__== '__main__':
    import doctest
    doctest.testmod()
    from time import time, clock
    L = list(range(1000))
    shuffle(L)
    start = time()
    quick(L)
    print("quick sort: {} for {} items".format(time() - start, len(L)))
    start = time()
    merge_sort(L)
    print("merge sort: {} for {} items".format(time() - start, len(L)))

Logically, both algorithm should take roughly the same time. Yet, as we increased the size of the list, this happened:

quick sort: 0.0055048465728759766 for 1000 items
merge sort: 0.013010978698730469 for 1000 items
quick sort: 0.06204104423522949 for 10000 items
merge sort: 0.44429707527160645 for 10000 items
quick sort: 0.7655110359191895 for 100000 items
merge sort: 47.87060809135437 for 100000 items

This goes against what we expect entirely. Why did this happen? As it turns out, the problem exists on the line while L1[i1:] and L2[i2:]: within the function merge(L1, L2). 

Splicing a list in python does not have complexity O(1) as we'd expect (i.e. constant time). Some research reveals that splicing actually have complexity O(k). The k in this case is not a constant - it is some variable unrelated to n. This means that splicing grows linearly, but does not necessarily grow according to the size of the list.

We can verify this with a quick function:

from random import shuffle, randint
from time import time, clock

def splice(L: list) -> []:    
    return L[:]

if __name__== '__main__':
    import doctest
    doctest.testmod()
    L = list(range(100000))
    start = time()
    splice(L)
    print("splicing takes {} for {} items".format(time() - start, len(L)))    

Notice has as the size of a list increase, the time it takes to splice a list also increase:

splicing takes 0.0010027885437011719 for 100000 items
splicing takes 0.010010957717895508 for 1000000 items
splicing takes 0.08705687522888184 for 10000000 items

Since comparisons do indeed take linear time, changing the while condition to a comparison managed to resolve this issue.

def merge(L1, L2):
    """return merge of L1 and L2

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([1, 2, 3], [0, 4, 5])
    [0, 1, 2, 3, 4, 5]
    >>> merge([0], [1, 2, 3, 4])
    [0, 1, 2, 3, 4]
    """
    L = []
    i1, i2 = 0, 0
    while i1 < len(L1) and i2 < len(L2):
        if L1[i1] < L2[i2]:
            L.append(L1[i1])
            i1 += 1
        else:
            L.append(L2[i2])
            i2 += 1
    return L + L1[i1:] + L2[i2:]

quick sort: 10.197987079620361 for 1000000 items
merge sort: 16.52327299118042 for 1000000 items

Now Merge sort and Quick sort grows according to the complexity O(n log n) as expected. However, this leaves one more question unanswered. If both Quick sort and Merge sort has time complexity O(n log n), why is Quick sort performing better for a randomized list? Unfortunately, I don't have the answer this week. Maybe more research will yield the answer next week!