Merge Sort

Проблема

Все алгоритмы сортировки сравнением, рассмотренные ранее (пузырьковая, выбором, вставками), гарантированно требуют O(n²) сравнений в худшем случае на больших массивах - для миллиона элементов это триллион операций. Нужен алгоритм, который использует принцип «разделяй и властвуй», чтобы гарантированно уложиться в O(n log n) независимо от исходного порядка данных.

Решение

Если массив состоит из 0 или 1 элемента, он уже отсортирован. Иначе массив делится пополам, каждая половина сортируется тем же алгоритмом рекурсивно, а затем две уже отсортированные половины сливаются в один массив: на каждом шаге слияния сравниваются «головы» двух половин, и меньший элемент забирается в результат. Деление даёт log n уровней рекурсии, а слияние на каждом уровне стоит O(n) - итого O(n log n).

Как это работает

Возьмём конкретный массив из 8 элементов: [5, 2, 8, 1, 9, 3, 7, 4]. Деление пополам даёт [5,2,8,1] и [9,3,7,4], каждая половина делится снова до [5,2]/[8,1] и [9,3]/[7,4], а затем ещё раз - до восьми массивов по одному элементу. От исходного размера 8 до базового случая размера 1 потребовалось ровно 3 деления пополам - это и есть log2(8) = 3, глубина рекурсии для этого конкретного n.

Эта формула масштабируется предсказуемо: для миллиона элементов log2(1 000 000) ≈ 19.93, значит потребуется около 20 уровней рекурсии - независимо от того, в каком порядке стояли исходные элементы. У сортировки вставками или пузырьком такой гарантии нет: их число проходов растёт вместе с n, а не с log n, так что разрыв между 20 и n становится огромным уже на массивах в тысячи элементов.

Разберём саму функцию merge на конкретном примере: left = [2, 5, 8], right = [1, 3, 9]. Указатели i и j стартуют с 0. Шаг 1: 2 против 1 - берём 1 из right, j = 1. Шаг 2: 2 против 3 - берём 2 из left, i = 1. Шаг 3: 5 против 3 - берём 3, j = 2. Шаг 4: 5 против 9 - берём 5, i = 2. Шаг 5: 8 против 9 - берём 8, i = 3, цикл заканчивается, потому что left исчерпан. Остаётся дописать хвост right.slice(2) = [9] - итог [1, 2, 3, 5, 8, 9] за 5 сравнений на 6 элементов.

Отсюда видно, откуда берётся итоговая формула сложности. На каждом уровне рекурсии сумма размеров всех подмассивов, которые нужно слить, равна n - на верхнем уровне это одно слияние n/2 + n/2, на следующем два слияния по n/4 + n/4 каждое, и так далее. Каждое слияние занимает время, пропорциональное сумме размеров сливаемых половин, значит весь уровень стоит O(n) независимо от того, на сколько отдельных слияний он разбит. Уровней log n, поэтому итог - O(n log n).

Устойчивость - не побочный эффект, а прямое следствие одной строки кода: if (left[i] <= right[j]). Представим сортировку заказов по полю total, где два заказа имеют одинаковую сумму total: 500, но разное поле id - A (id: 12) пришёл раньше B (id: 47) в исходном массиве. Если A окажется в left, а B - в right, условие <= при равенстве сумм заберёт A первым, сохранив исходный порядок между ними. Замени <= на <, и при равенстве всегда выигрывал бы right - устойчивость терялась бы незаметно, без единой ошибки на этапе выполнения.

Про память стоит уточнить деталь, которую часто упрощают до «O(n) дополнительной памяти». Учебники обычно описывают вариант с одним общим буфером размером n, используемым повторно на всех уровнях. Реализация на этой странице устроена иначе: arr.slice(0, mid) и arr.slice(mid) создают новые массивы на каждом рекурсивном вызове. На каждом уровне суммарно копируется n элементов (как и в самом слиянии), а уровней log n - значит за весь запуск выполняется порядка n log n операций копирования, просто не одновременно: массивы предыдущих уровней уже освобождены сборщиком мусора к моменту, когда создаются следующие. Пиковая одновременная память всё ещё O(n), но общее число выделенных ячеек за всё время работы - O(n log n), а не O(n).

Существует и итеративная (bottom-up) версия того же алгоритма: вместо рекурсивного деления сверху вниз она сразу сливает пары соседних элементов размером 1, затем результаты по 2, потом по 4, и так далее - удваивая размер сливаемых блоков на каждой итерации внешнего цикла. Итоговая сложность та же O(n log n), но без единого рекурсивного вызова и без связанного с ним расхода стека - на встраиваемых системах с жёстким лимитом глубины стека это не косметическая деталь, а условие, без которого рекурсивная версия просто упадёт на достаточно большом входе.

Сортировка слиянием старше большинства алгоритмов в этом разделе: её описал Джон фон Нейман в 1945 году в отчёте о первом компьютере EDVAC, ещё до того, как термин «алгоритм сортировки» стал общеупотребимым в информатике. Идея разделять задачу на независимые половины и сливать готовые решения - один из первых зафиксированных примеров техники divide-and-conquer, к которой позже свели quicksort, быстрое умножение матриц (алгоритм Штрассена) и множество других алгоритмов.

Нюансы выбора

Против Quicksort - Quicksort в среднем быстрее за счёт меньших констант и сортировки на месте, но его худший случай O(n²) реален на специально подобранных или уже почти отсортированных данных при плохом выборе опорного элемента. Merge sort выбирают, когда нужна гарантия «никогда не хуже O(n log n)», а не просто хорошее среднее поведение.

Против Heap Sort - оба дают гарантированный O(n log n) и оба используют O(1)-O(n) дополнительной памяти по-разному, но Heap Sort не устойчив, а его доступ к памяти скачет по индексам кучи, что плохо для кэша процессора. Merge sort проходит по данным последовательно, поэтому на реальном железе часто оказывается быстрее, несмотря на одинаковую асимптотику.

На маленьких подмассивах - гибридные реализации (Timsort, стандартные библиотеки C++/Java) переключаются на insertion sort ниже порога примерно в 32-64 элемента (конкретное значение - MIN_MERGE в Timsort), потому что накладные расходы на рекурсивные вызовы перевешивают выигрыш от O(n log n) на настолько маленьких n.

Для многостороннего внешнего слияния - когда данные разбиты на k отсортированных кусков на диске (например, после параллельной обработки), merge sort обобщается до k-стороннего слияния через мин-кучу размером k, читая по одной записи из каждого куска - Quicksort здесь неприменим напрямую, потому что ему нужен произвольный доступ ко всем данным сразу.

Не выбирать для памяти-ограниченных встраиваемых систем - когда доступно, скажем, 2КБ RAM на массив в 500 элементов, O(n) дополнительной памяти merge sort может просто не поместиться, тогда как in-place Heap Sort или Shell Sort с O(1) памяти работают в тех же границах без компромиссов по гарантии сложности.

Примеры в коде

John von Neumann, 1945 - первое задокументированное описание merge sort появилось в отчёте о компьютере EDVAC, написанном фон Нейманом и Германом Голдстайном; это один из самых ранних формально описанных алгоритмов в истории вычислительной техники, задолго до появления самого термина «divide-and-conquer».

`java.util.Arrays.sort(Object[])` до сих пор явно требует устойчивую сортировку по контракту JavaDoc и реализована через модифицированный merge sort (а с Java 7 - через TimSort) именно потому, что сортировка объектов по одному полю обязана сохранять порядок по остальным - для массивов примитивов (int[], double[]) тот же метод использует dual-pivot quicksort, где устойчивость не имеет смысла.

`std::stable_sort` в C++ STL гарантирует устойчивость по стандарту и обычно реализуется как merge sort; если дополнительная память для буфера недоступна, реализация откатывается на медленный in-place merge с ухудшением сложности до O(n log²n) - явный компромисс «время за память», прописанный прямо в стандарте библиотеки.

`lib/list_sort.c` в ядре Linux реализует bottom-up merge sort специально для связных списков (struct list_head), используемый несколькими подсистемами ядра для сортировки очередей и списков устройств - выбор объясняется тем же свойством, что и в общей теории: слияние связных списков не требует произвольного доступа, которого списки не дают.

Apache Spark на этапе shuffle (sortByKey, repartitionAndSortWithinPartitions) сортирует данные, которые не помещаются в память одного узла, разбивая их на отсортированные куски на диске и сливая через внешний многосторонний merge - тот же принцип, что и в базах данных, но в масштабе распределённого кластера.

Когда применять

• Когда важна гарантия O(n log n) в худшем случае (например, real-time системы, где недопустим квадратичный «срыв»).
• Когда нужна устойчивая сортировка, а не только быстрая.
• Для сортировки связных списков, где произвольный доступ дорог, но последовательное слияние - нет.

Примеры из практики

• Timsort (Python sorted(), Java Arrays.sort() для объектов) - гибрид сортировки слиянием и вставками, использующий именно устойчивость и гарантированную асимптотику слияния.
• Внешняя сортировка больших файлов - база данных сортирует куски, помещающиеся в память, а затем сливает их с диска, что является прямым применением merge-шага.
• Git использует вариант слияния при трёхстороннем merge истории коммитов (концептуально близкий принцип объединения двух упорядоченных последовательностей).