python3 merge sort

 

import pdb

sorted = [0, 0, 0, 0, 0, 0, 0, 0] # cache for sorting

def merge(lst, m, middle, n):

    global sorted

    i = m

    j = middle + 1

    pos = m

    

    while i <= middle and j <= n:

        if lst[i] < lst[j]:

            sorted[pos] = lst[i]

            i+=1

        else:

            sorted[pos] = lst[j]

            j+=1

        pos+=1

    # insert part of remaining list

    if i > middle:

        for idx in range(pos, n+1):

            sorted[idx] = lst[j]

            j+=1

    else:

        for idx in range(pos, n+1):

            sorted[idx] = lst[i]

            i+=1

    

    # apply part of aligned list

    for idx in range(m, n+1):

        lst[idx] = sorted[idx]

        

    print("mergeSort({})".format(lst))

            

def mergeSort(lst, m, n):

     

    if m < n:

        middle = int((m+n)/2)

        mergeSort(lst, m, middle)

        mergeSort(lst, middle+1, n)

        merge(lst, m, middle, n)

    

if __name__ == '__main__':

    rawList = [3, 5, 2, 1, 8, 10, 11, 9]

    mergeSort(rawList, 0, len(rawList)-1)

    

    print(rawList)