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))
In [ ]: