Merge sort and test function. merge sort code from http://interactivepython.org/runestone/static/pythonds/SortSearch/TheMergeSort.html

mergeSort.py

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()

Output : omit many_times_test()

alist [3, 9, 4, 1, 0, 8, 7, 5, 2, 6]
Splitting [3, 9, 4, 1, 0, 8, 7, 5, 2, 6]
Splitting [3, 9, 4, 1, 0]
Splitting [3, 9]
Splitting [3]
Splitting [9]
Merging [3, 9]
Splitting [4, 1, 0]
Splitting [4]
Splitting [1, 0]
Splitting [1]
Splitting [0]
Merging [0, 1]
Merging [0, 1, 4]
Merging [0, 1, 3, 4, 9]
Splitting [8, 7, 5, 2, 6]
Splitting [8, 7]
Splitting [8]
Splitting [7]
Merging [7, 8]
Splitting [5, 2, 6]
Splitting [5]
Splitting [2, 6]
Splitting [2]
Splitting [6]
Merging [2, 6]
Merging [2, 5, 6]
Merging [2, 5, 6, 7, 8]
Merging [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sorted alist [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
alist using python sorted [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]