MergeSort.py

#We are doing a ascending order sort.
def merge(A,B):
    (C,m,n)=([],len(A),len(B))#Initiating elements
    (i,j)=(0,0)
    while i+j < m+n : #i+j is number of elements merged so far
        if i==m: #List A is empty
            C.append(B[j])
            j=j+1
        elif j==n: #List B is empty
            C.append(A[i])
            i=i+1
        elif A[i] <= B[j]: #A is smaller 
            C.append(A[i])
            i=i+1
        elif A[i] >= B[j]: #B is smaller
            C.append(B[j])
            j=j+1
    return(C)

def mergesort(A,left,right):
    # Sort the slice A[left:right]
    if right-left <= 1: #If there is only one element or less than one, We don't need to sort it.
        return(A[left:right])
    if right-left > 1: #Recursive Call
        mid=(right+left)//2
        L=mergesort(A,left,mid)
        R=mergesort(A,mid,right)
        return(merge(L,R))