merge_sort

# import random
arr = [9, 1, 4, 45, 16, 64, 37, 34, 45, 65, 76]


# for 0 in 100:

# arr.append(random.randint(1,100))

def merge(left, right, array):
    i, j, k = (0, 0, 0)
    h = len(right)-1
    m = len(left)-1
    while i <= m and j <= h:
        if left[i] < right[j]:
            array[k] = left[i]
            k += 1
            i += 1
        else:
            array[k] = right[j]
            k += 1
            j += 1
    while i <= m:
        array[k] = left[i]
        k += 1
        i += 1
    while j <= h:
        array[k] = right[j]
        k += 1
        j += 1



def merge_sort(array):
    n = len(array)
    if n < 2:
        return n
    if n >= 2:
        m = int(n / 2)
        left = array[:m]
        right = array[m:]
        merge_sort(left)
        merge_sort(right)
        merge(left, right, array)

merge_sort(arr)
print(arr)