import random


def mergesort(a):

    l = len(a)
    if l < 2:
        return a

    array_left = a[: l // 2]
    array_right = a[l // 2 :]

    array_left = mergesort(array_left)
    array_right = mergesort(array_right)

    return merge(array_left, array_right)


def merge(array_left, array_right):
    array_merged = []
    while array_left or array_right:
        if array_left and array_right:
            array_merged.append(
                array_left.pop(0)
                if array_left[0] < array_right[0]
                else array_right.pop(0)
            )
        elif array_left:
            array_merged.extend(array_left)
            break
        elif array_right:
            array_merged.extend(array_right)
            break

    return array_merged


a = [random.randint(1, 100) for i in range(100)]
a = mergesort(a)
print(a)
assert all(a[i] <= a[i + 1] for i in range(len(a) - 1))

