def mergeSort(alist):
    print("Splitting ", alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i+=1
            else:
                alist[k] = righthalf[j]
                j+=1
            k+=1

        while i<len(lefthalf):
            alist[k] = lefthalf[i]
            i+=1
            k+=1
            
        while j<len(righthalf):
            alist[k] = righthalf[j]
            j+=1
            k+=1

        print("Merging ", alist)

import random
def mergeSortTest(number):
    alist = list(range(number))
    random.shuffle(alist)
    print("alist ", alist)
    blist = alist[:]
    mergeSort(alist)
    blist = sorted(blist)
    
    print("sorted alist ", alist)
    print("alist using python sorted", blist)
    assert alist == blist

mergeSortTest(10)

def many_times_test():
    testSet = list(range(random.randrange(100)))
    for n in testSet:
        mergeSortTest(n)

many_times_test()