Как работает сортировка слиянием?

Алгоритм:

1. если в массиве 0 или 1 элемент — он отсортирован;
2. разделить массив на две половины;
3. рекурсивно отсортировать каждую;
4. слить две отсортированные половины в одну.

Слияние — два указателя на начала половин. На каждом шаге берём меньший из двух текущих элементов и переносим в результат; когда одна половина кончилась, дописываем остаток другой. Это O(n) для двух половин суммарной длины n. Если при равенстве брать элемент из левой половины, сохраняется исходный порядок равных — сортировка устойчива.

Сложность. Глубина деления — log₂ n уровней, на каждом уровне сливается ровно n элементов. Итого O(n log n) в любом случае — нет худшего случая, как у быстрой сортировки. Цена — O(n) дополнительной памяти под временный массив.

Где особенно хороша:

• внешняя сортировка — данные не помещаются в память: сортируем куски, пишем на диск и сливаем потоками (так работают базы данных и сортировка больших файлов);
• связные списки — слияние не требует произвольного доступа и дополнительной памяти под массив;
• там, где нужна устойчивость — основа Timsort.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:          # <= сохраняет устойчивость
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]