def merge_sort(array, left, right):

    if left < right:

        middle = (left + right) // 2

        print(f"Splitting array into {array[left:middle]} and {array[middle:right]}.")

        merge_sort(array, left, middle)

        merge_sort(array, middle + 1, right)

        print(f"Merging {array[left:middle]} and {array[middle:right]}.")

        return merge(array, left, middle, right)

    else:

        return array[left:right + 1]

def merge(array, left, middle, right):

    result = []

    i, j = left, middle + 1

    while i <= middle and j <= right:

        if array[i] <= array[j]:

            result.append(array[i])

            i += 1

        else:

            result.append(array[j])

            j += 1

    result += array[i:middle + 1]

    result += array[j:right + 1]

    return result

def main():

    array = [12, 11, 13, 5, 6, 7, 1, 2, 3, 4]

    print("Original array:", array)

    sorted_array = merge_sort(array, 0, len(array) - 1)

    print("Sorted array:", sorted_array)

if __name__ == "__main__":

    main()