MergeSort_Python

def merge(arr, s1, e1, s2, e2):
    l = []
    i, j = s1, s2

    while i <= e1 and j <= e2:
        if arr[i] < arr[j]:
            l.append(arr[i])
            i += 1
        else:
            l.append(arr[j])
            j += 1
    while i <= e1:
        l.append(arr[i])
        i += 1
    while j <= e2:
        l.append(arr[j])
        j += 1

    for k in range(s1, e2+1):
        arr[k] = l[k-s1]

def mergesort(arr, s, e):
    if e > s:
        mergesort(arr, s, s+(e-s)//2)
        mergesort(arr, s+(e-s)//2+1, e)
        merge(arr, s, s+(e-s)//2, s+(e-s)//2+1, e)

if __name__ == "__main__":
    n = int(input())
    arr = list(map(int, input().split()))
    mergesort(arr, 0, n-1)
    for i in arr:
        print(i, end = ' ')