MergeSort

A less basic sorting algorithm that splits a sequence in two, then orders them splits...



In [1]:

    
def mergesort(seq):
    mid = len(seq)//2
    lft, rgt = seq[:mid],seq[mid:]
    if len(lft) > 1:
        lft = mergesort(lft)
    if len(rgt) > 1:
        rgt = mergesort(rgt)
    res =[]
    while lft and rgt:
        if lft[-1] > rgt[-1]:
            res.append(lft.pop())
        else:
            res.append(rgt.pop())
    res.reverse()
    return (lft or rgt) + res



In [8]:

    
import random
lst = list(range(10))
seq = random.sample(lst, 10)
print seq









    



[0, 1, 7, 9, 3, 8, 4, 5, 2, 6]



In [9]:

    
mergesort(seq)









    Out[9]:





[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Perfect that works also! Note you cannot use numpy arrays with pop I will look up the correct notation. Though you could always use numpyarray.tolist().



In [ ]: