Understanding MergeSort :D

understanding_mergesort.py

## DIVIDE -> mergesort
## CONQUER -> mergesort
## COMBINE -> merge

def merge(S1, S2, S):
    '''
    S1-> First sorted seq
    S2-> Second sorted seq
    S -> Original seq
    '''
    i = j = 0
    while i+j < len(S):
        if j==len(S2) or (i<len(S1) and S1[i]<S2[j]):
            S[i+j] = S1[i]
            i+=1
        else:
            S[i+j]=S2[j]
            j+=1
        print("[MERGE] Array after merging: ", S)
    


def mergesort(S):
    '''
    S -> Seq to be sorted
    '''
    n = len(S)
    if n<2:
        print("[RETURN] recursive call popped from stack")
        return
    #DIVIDE
    mid = n//2
    S1 = S[0:mid]
    print("[S1] First half: ", S1, end=" ")
    S2 = S[mid:n]
    print("| [S2] First half: ", S2)
    #CONQUER
    print("[1st] Mergesort Call")
    mergesort(S1)
    print("[2st] Mergesort Call")
    mergesort(S2)
    #MERGE
    print("[MERGE] Merge Call")
    merge(S1, S2, S)

S = [6,2,4,1,7,9,8,3]
print("[UNSORTED] unsorted array: ", S)
print("[START] MERGE SORT USING DIVIDE AND CONQUER")
mergesort(S)
print("[FINISHED] MERGE SORT USING DIVIDE AND CONQUER")
print("[SORTED] sorted array: ", S)