Merge Sort does logn merge steps because each merge step doubles the list size
It does n work for each merge step because it must look at verty item.


In [1]:
# References http://stackoverflow.com/questions/18761766/mergesort-python

In [12]:
def merge_sort(a):
    
    if len(a) < 2:
        return a
    
    result = []
    mid = len(a) // 2
    
    lo_a = merge_sort(a[:mid])
    hi_a = merge_sort(a[mid:])
        
    # merging two part of array
    i = 0 # iterator for `lo_a`
    j = 0 # iterator for `hi_a`
    while i < len(lo_a) and j < len(hi_a) :
        if lo_a[i] < hi_a[j]:
            result.append(lo_a[i])
            i +=1
        else:
            result.append(hi_a[j])
            j +=1
            
    # merge the rest
    result.extend(lo_a[i:])
    result.extend(hi_a[j:])
    
    return result

In [13]:
alist = [34,2,24,12, 45,33,9,99]
print(merge_sort(alist))


[2, 9, 12, 24, 33, 34, 45, 99]

In [ ]: