Сортировка слиянием — классический алгоритм «разделяй и властвуй»: делим массив пополам, рекурсивно сортируем половины и сливаем две отсортированные половины за O(n). Время работы O(n log n) в любом случае, сортировка устойчива, но требует O(n) дополнительной памяти. Про деревья рекурсии см. разделяй и властвуй.
Слияние двух отсортированных списков
Смотрим на начала обоих списков и переносим меньший элемент в результат. Когда один список закончился, дописываем остаток другого: он уже отсортирован. Это O(n + m). При равенстве берём элемент из левого списка, поэтому слияние устойчиво.
def merge(left, right):
out = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out += left[i:]
out += right[j:]
return out
print(merge([1, 4, 7], [2, 3, 9]))
print(merge([], [5]))
print(merge([(1, "a"), (2, "a")], [(1, "b"), (2, "b")]))[1, 2, 3, 4, 7, 9]
[5]
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]Рекурсивная сортировка слиянием
Список из 0 или 1 элемента уже отсортирован. Иначе делим список пополам, сортируем половины и сливаем их.
