def merge(lst1, lst2):
    """ merging two ordered lists using
        the two pointer algorithm """
    n1 = len(lst1)
    n2 = len(lst2)
    lst3 = [0 for i in range(n1 + n2)]  # alocates a new list
    i = j = k = 0  # simultaneous assignment
    while (i < n1 and j < n2):
        if (lst1[i] <= lst2[j]):
            lst3[k] = lst1[i]
            i = i +1
        else:
            lst3[k] = lst2[j]
            j = j + 1
        k = k + 1  # incremented at each iteration
    lst3[k:] = lst1[i:] + lst2[j:]  # append remaining elements
    return lst3



def mergesort(lst):
    """ recursive mergesort """
    n=len(lst)
    if n <= 1: 
        return lst
    else:
        return merge(mergesort(lst[0:n//2]),mergesort(lst[n//2:n]))
                #two recursive calls


from quicksort import *

print("3 way race")
for func in [quicksort, mergesort, sorted]:
    print(func.__name__)

    for n in [200, 400, 800]:
        print("n=", n, end=" ")
        rlst = randlist(n)

        t0 = time.clock()
        for i in range(100):
            func(rlst) #sort is not inplace, so lst remains unchanged !
        t1 = time.clock()
        print(t1-t0)