import random

def merge_sort(a):
    n = len(a)
    if n <=1:
        return a
    a1 = merge_sort(a[:n//2])
    a2 = merge_sort(a[n//2:])
    return merge(a1, a2)

def merge(a1, a2):
    i1, i2 = 0, 0
    n1, n2 = len(a1), len(a2)
    out = list()
    while len(out) < n1 + n2:
        if i1 == n1:
            out.append(a2[i2])
            i2 += 1
        elif i2 == n2:
            out.append(a1[i1])
            i1 += 1
        elif a1[i1] < a2[i2]:
            out.append(a1[i1])
            i1 += 1
        else:
            out.append(a2[i2])
            i2 += 1
    return out

if __name__ == "__main__":
    n = 16
    a = [i+1 for i in range(n)]
    random.shuffle(a)
    print(a)
    b = merge_sort(a)
    print(b)