*Merge Sort - ALawliet/algorithms GitHub Wiki

def mergesort(A, l, r):
    if l < r:
        m = (l+r) // 2
        mergesort(A, l, m)
        mergesort(A, m+1, r)
        merge(A, l, m, r)

def merge(A, l, m, r):
    L = A[l:m+1]
    R = A[m+1:]

    i = 0
    j = 0
    k = p
    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1

    if i < len(L):
        A[k:r+1] = L[i:]
    if j < len(R):
        A[k:r+1] = R[j:]

def mergeSort(myList):
    if len(myList) > 1:
        mid = len(myList) // 2
        left = myList[:mid]
        right = myList[mid:]

        # Recursive call on each half
        mergeSort(left)
        mergeSort(right)

        # Two iterators for traversing the two halves
        i = 0
        j = 0
        
        # Iterator for the main list
        k = 0
        
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
              # The value from the left half has been used
              myList[k] = left[i]
              # Move the iterator forward
              i += 1
            else:
              myList[k] = right[j]
              j += 1
            # Move to the next slot
            k += 1

        # For all the remaining values
        while i < len(left):
            myList[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            myList[k] = right[j]
            j += 1
            k += 1

myList = [54,26,93,17,77,31,44,55,20]
mergeSort(myList)
print(myList)