def merge_sort(array):
    """split and recursively sort an array"""

    if len(array) <= 1:
        return array

    mid = len(array) // 2
    left_slice = array[:mid]
    right_slice = array[mid:]

    return merge(merge_sort(left_slice), merge_sort(right_slice))


def merge(left, right):
    """merge 2 sorted arrays"""
    sorted_array = []
    i, j = 0, 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1

    # add remaining items, if any
    sorted_array.extend(left[i:])
    sorted_array.extend(right[j:])
    return sorted_array


import random


def generate_random_list(size):
    return random.sample(range(size), size)


a = generate_random_list(1000)
b = merge_sort(a)

print(f"random array : \n{a}")
print(f"sorted array : \n{b}")