In [56]:

    

def merge(a, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    L, R = [], []
    for i in range(0, n1):
        L.append(a[i + p])
    for j in range(0, n2):
        R.append(a[j + q + 1])
    i, j = 0, 0
    for k in range(p, r):
        if i <= len(L) and (j >= len(R) or L[i] <= R[j]):
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1


    

In [47]:

    

import math

def mergeSort(a, p, r):
    if p < r:
        mid = math.floor((p + r)/2)
        mergeSort(a, p, mid)
        mergeSort(a, mid + 1, r)
        merge(a, p, mid, r)


    

In [57]:

    

a = [3, 4, 1, 2]
mergeSort(a, 0, 3)
print(a)


    

    




[1, 2, 3, 2]

In [37]:

    

a = [3, 4, 1, 2]
merge(a, 0, 1, 3)
print(a)


    

    




[1, 2, 3, 4]

In [ ]: