# merge sort

lst = []  # declaring list l

n = int(input("Enter number of elements in the list: "))  # taking value from user

for i in range(n):
    temp = int(input("Enter element" + str(i + 1) + ": "))
    lst.append(temp)


def merge(ori_lst, left, mid, right):
    L, R = [], []  # PREPARE TWO TEMPORARY LIST TO HOLD ELEMENTS
    for i in range(left, mid):  # LOADING
        L.append(ori_lst[i])
    for i in range(mid, right):  # LOADING
        R.append(ori_lst[i])
    base = left  # FILL ELEMENTS BACK TO ORIGINAL LIST START FROM INDEX LEFT
    # EVERY LOOP CHOOSE A SMALLER ELEMENT FROM EITHER LIST
    while len(L) > 0 and len(R) > 0:
        if L[0] < R[0]:
            ori_lst[base] = L[0]
            L.remove(L[0])
        else:
            ori_lst[base] = R[0]
            R.remove(R[0])
        base += 1
    # UNLOAD THE REMAINER
    while len(L) > 0:
        ori_lst[base] = L[0]
        L.remove(L[0])
        base += 1
    while len(R) > 0:
        ori_lst[base] = R[0]
        R.remove(R[0])
        base += 1
    # ORIGINAL LIST SHOULD BE SORTED FROM INDEX LEFT TO INDEX RIGHT


def merge_sort(L, left, right):
    if left + 1 >= right:  # ESCAPE CONDITION
        return
    mid = left + (right - left) // 2
    merge_sort(L, left, mid)  # LEFT
    merge_sort(L, mid, right)  # RIGHT
    merge(L, left, mid, right)  # MERGE


print("UNSORTED -> ", lst)
merge_sort(lst, 0, n)
print("SORTED -> ", lst)