Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
738 B
2
Indexable
import math
def merge(arr1, arr2, m, n):
    f_ptr = 0
    s_ptr = 0
    tmp = []
    while f_ptr < m and s_ptr < n:
        if arr1[f_ptr] < arr2[s_ptr]:
            tmp.append(arr1[f_ptr])
            f_ptr += 1
        else:
            tmp.append(arr2[s_ptr])
            s_ptr += 1
    tmp += arr1[f_ptr:m] + arr2[s_ptr:n]
    return tmp

def merge_sort(arr):
    if len(arr) == 1:
        return arr
    print("Merging arr:", *arr)
    left = merge_sort(arr[:math.ceil(len(arr)/2)])
    right = merge_sort(arr[math.ceil(len(arr)/2):])
    return merge(left, right, len(left), len(right))

if __name__ == "__main__":
    n = int(input())
    arr = list(map(int, input().split()))
    arr = merge_sort(arr)
    print("Answer:", *arr)