F. Сортировка слиянием

Мы уже реализовывали функцию merge, которая способна “слить” два отсортированных списка в один.
Чаще всего её применяют в рекурсивном алгоритме сортировки слиянием.

Напишите рекурсивную функцию merge_sort, которая производит сортировку списка.

Примечание

Ваше решение должно содержать только функции.
В решении не должно быть вызовов требуемых функций, за исключением рекурсивных.
Трассировка вызова рекурсивной функции в обработке ответа не учитывается и показана для примера.

Пример

Ввод

result = merge_sort([3, 2, 1])

Вывод

# Вызов merge_sort([3, 2, 1])
# Вызов merge_sort([3])
# Вызов merge_sort([2, 1])
# Вызов merge_sort([2])
# Вызов merge_sort([1])
result = [1, 2, 3]

Ввод

result = merge_sort([3, 1, 5, 3])

Вывод

# Вызов merge_sort([3, 1, 5, 3])
# Вызов merge_sort([3, 1])
# Вызов merge_sort([3])
# Вызов merge_sort([1])
# Вызов merge_sort([5, 3])
# Вызов merge_sort([5])
# Вызов merge_sort([3])
result = [1, 3, 3, 5]

Решение

Отличная задача для того, чтобы прочувствовать всю красоту рекурсии. Мы уже умеем сортировать слиянием отсортированные списки, теперь попробуем отсортировать один неотсортированный.

Для того, чтобы решить эту задачу нам надо прийти к двум умозаключениям:
1) любой список можно разбить на примерно равные два списка
2) если каждый из двух списков содержит один или ноль элементов, то можно их отдать на “слияние” и получить отсортированный список, который можно в свою очередь тоже отдать на слияние

Если поразмыслить над этими условиями, то “план войны” становится более-менее понятным.
В момент погружения: Делим списки на части до тех пор пока любая из частей не будет пустой или содержать только один элемент.
В момент всплытия: Сливаем полученные списки.

Поздравляю, вы только что реализовали одну из самых эффективных сортировок!

def merge(left, right):
    result = []
    pos_left = pos_right = 0

    while pos_left < len(left) and pos_right < len(right):
        if left[pos_left] < right[pos_right]:
            result.append(left[pos_left])
            pos_left += 1
        else:
            result.append(right[pos_right])
            pos_right += 1

    result += left[pos_left:]
    result += right[pos_right:]

    return result


def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)