Сортировка слиянием: алгоритм, придуманный фон Нейманом ещё до настоящих компьютеров

Этот алгоритм сортировки описали раньше, чем появились компьютеры, на которых его можно было запустить — и он до сих пор работает там, где нельзя рисковать.

Джон фон Нейман сформулировал сортировку слиянием в 1945 году. Это один из самых ранних описанных нетривиальных алгоритмов вообще.

Идея: разделяй и властвуй

Сортировать большой массив трудно. А сортировать массив из одного элемента — нечего делать, он уже отсортирован. Сортировка слиянием строится на этом наблюдении и работает по принципу «разделяй и властвуй»:

1. Раздели массив пополам.
2. Отсортируй каждую половину тем же способом (рекурсия).
3. Слей две отсортированные половины в один отсортированный массив.

Деление продолжается, пока куски не уменьшатся до одного элемента — а они тривиально отсортированы. Затем начинается обратный ход: маленькие отсортированные куски сливаются во всё более крупные, пока не соберётся весь массив.

Главный трюк — слияние

Вся сила в шаге «слить». Сливать уже отсортированные части очень дёшево: ставим два пальца на начала обеих половин, сравниваем то, на что они указывают, и переносим в результат меньший элемент, сдвигая соответствующий палец. Поскольку обе половины упорядочены, нам ни разу не нужно возвращаться или перепроверять — каждый элемент трогается ровно один раз. Слияние двух частей суммарной длины $k$ занимает $O(k)$.

def merge(left, right):
    result = []
    i = j = 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
    result.extend(left[i:])         # хвост одной из частей
    result.extend(right[j:])
    return result

def merge_sort(arr):
    if len(arr) <= 1:               # один элемент уже отсортирован
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # сортируем половины рекурсивно
    right = merge_sort(arr[mid:])
    return merge(left, right)       # и сливаем

data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data))   # [3, 9, 10, 27, 38, 43, 82]

Почему всегда O(n log n)

Глубина рекурсии — $\log_2 n$: столько раз можно делить массив пополам, пока не дойдём до единиц. На каждом из этих уровней суммарно сливается ровно $n$ элементов (части разные, но в сумме это весь массив). Перемножаем — и получаем:

$$T(n) = \underbrace{\log_2 n}_{\text{уровней}} \times \underbrace{O(n)}_{\text{слияние на уровне}} = O(n \log n)$$

Ключевое слово — гарантированно. В отличие от быстрой сортировки, у которой бывает «злой» вход с деградацией до $O(n^2)$, у слияния худший случай совпадает со средним. Никаких сюрпризов: $O(n \log n)$ на любых данных, хоть на отсортированных, хоть на обратных, хоть на случайных.

Два важных свойства

Первое — устойчивость (stability): равные элементы сохраняют исходный взаимный порядок (за это отвечает <= в слиянии). Это критично, когда сортируешь по нескольким ключам подряд. Второе — слияние прекрасно работает с последовательным доступом и не требует, чтобы все данные помещались в память сразу. Поэтому именно сортировку слиянием применяют для внешней сортировки: когда данных столько, что они не влезают в оперативную память и лежат на диске, их сливают порциями.

Где её выбирают

Сортировка слиянием — основа гибридного алгоритма Timsort, который сортирует списки в Python и массивы объектов в Java: он опирается на слияние и хитро использует уже упорядоченные участки. Её предсказуемость и устойчивость ценят в системах, где нельзя допустить случайную деградацию, и в обработке огромных файлов, не влезающих в память.

Мораль

Сортировка слиянием — эталон стиля «разделяй и властвуй»: свести задачу к двум вдвое меньшим, а потом дёшево объединить ответы. Платим за это лишней памятью под результат слияния, зато получаем железную гарантию скорости и устойчивость. Когда важнее «никогда не медленно», чем «иногда чуть быстрее», выбирают именно слияние.