from random import randint


def merge_sort(lst):
    if len(lst) > 1:
        mid = int(len(lst)/2)
        left = lst[:mid]
        right = lst[mid:]

        # print(f'left\n\t{left}\nright\n\t{right}')
        merge_sort(left)
        merge_sort(right)

        i = 0  # position in left
        j = 0  # position in right
        k = 0  # position in output
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                # pull from left
                lst[k] = left[i]
                i += 1
            else:
                # pull from right
                lst[k] = right[j]
                j += 1
            k += 1
        while i < len(left):
            # right is empty, pull rest from left
            lst[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            # left is empty, pull rest from right
            lst[k] = right[j]
            j += 1
            k += 1
        # print(f'merged into {lst}')


def run():
    random_lst = [randint(0, 100) for i in range(10)]
    print(random_lst)
    merge_sort(random_lst)
    print(random_lst)


if __name__ == '__main__':
    run()