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

Представьте две сейсмические службы: одна ведёт каталог землетрясений западного полушария, другая — восточного, и каждая записывает события по времени. Нужна общая хроника, тоже по времени. Сваливать оба каталога в кучу и сортировать заново незачем: достаточно смотреть на первое непрочитанное событие каждой ленты и забирать более раннее. Ниже — настоящий каталог USGS, все 19 073 землетрясения силой от 5 за 2015–2025 годы, разделённые на две ленты. Карта вспыхивает в том порядке, в каком слияние забирает события. Переключите, как делить каталог: по полушариям или по глубине.

На 19 073 события ушло 19 070 сравнений: по одному на событие, пока не кончилась одна из лент, а последние три события второй ленты перенесены без сравнений. Обратите внимание на самую длинную серию из одной ленты при делении на запад и восток: 119 событий подряд пришли с востока. Серия начинается с землетрясения магнитудой 8,8 у Камчатки 29 июля 2025 года и продолжается в основном его повторными толчками: почти десять часов каждое следующее событие хроники приходило с востока.

Слияние: два указателя

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

Почему это верно: в каждом списке первый непрочитанный элемент — наименьший из оставшихся в этом списке, потому что список отсортирован. Значит, наименьший из всех оставшихся — один из двух элементов под указателями, и сравнение его находит. Результат растёт по одному элементу за сравнение, поэтому слияние списков длины m и k стоит не больше m + k − 1 сравнений и ровно m + k переносов. Последнее сравнение можно сэкономить всегда: когда в одном списке ничего не осталось, сравнивать не с чем.

Остаётся одна тонкость — равные элементы. Если первые непрочитанные равны, берём из левого списка. Тогда равные элементы выходят в том же порядке, в каком стояли, и сортировка получается устойчивой. В коде это одно условие: брать из правого списка, только если его элемент строго меньше.

Идея

Список из одного элемента уже отсортирован. Длинный список разрежем пополам, отсортируем каждую половину тем же способом и сольём две отсортированные половины в одну. Вся работа — в слияниях, а их на каждом уровне разрезания суммарно не больше n сравнений, уровней же всего log₂ n.

Рекурсия сначала дробит массив до кусочков по одному элементу, а потом собирает: из пар — четвёрки, из четвёрок — восьмёрки. Удобно смотреть на это как на турнир. В первом круге сливаются соседние кусочки по одному, во втором — получившиеся пары, и так до финала, где сливаются две отсортированные половины.

Турнир слияний

Вот все шестнадцать землетрясений 2025 года силой от 7, в порядке дат. Сверху — шестнадцать кусков по одному; каждая строка ниже сливает пары кусков строки выше. Справа на каждом уровне — сколько сравнений он стоил. Переключите порядок на входе: отсортированный заранее массив сливается дешевле, а по-настоящему плохого входа у слияния нет.

Посмотрите на счётчики уровней. На первом уровне восемь слияний пар, по одному сравнению на каждое: 8. Дальше слияния дороже, но на уровне всё равно не больше 16 сравнений: каждое сравнение переносит в результат один элемент, а элементов на уровне шестнадцать. На входе по датам вышло 8 + 12 + 12 + 14 = 46. Если вход уже отсортирован, каждое слияние заканчивается, как только кончилась левая половина, и делает столько сравнений, сколько в ней элементов: 8 + 8 + 8 + 8 = 32.

Почему n log n

Можно ли лучше? Любая сортировка, которая узнаёт о данных только из сравнений, в худшем случае делает не меньше log₂ n! ≈ n log₂ n − 1,44n сравнений — почему, рассказано в статье о нижней границе. Для шестнадцати элементов это 45, а худший случай слияния — 15 + 14 + 12 + 8 = 49: на каждом уровне каждое слияние экономит хотя бы одно сравнение. По порядку роста слияние оптимально, и даже константа почти не отличается от наилучшей возможной.

Код

В Python удобно возвращать новый список: срезы a[:mid] и a[mid:] копируют половины, слияние собирает третий список. Это просто, но тратит память на каждом уровне. В Go буфер выделяется один раз на всю сортировку: слияние пишет в него, а потом результат копируется обратно в массив. Счётчик counts собирает сравнения по уровням рекурсии — те же числа, что в сцене.

А это первая сцена в виде программы: каталог на сервере, три способа разделить его на две ленты и слияние обратно в одну хронику.

Сколько это стоит

Время — Θ(n log n) на любом входе: даже на отсортированном массиве слияние делает около (n/2) log₂ n сравнений и честно переписывает все элементы на каждом уровне. Это и достоинство, и недостаток: плохих входов нет, но и почти готовые данные досортировываются ненамного быстрее случайных. Память — O(n) на буфер плюс O(log n) на рекурсию. Слить два куска на месте, без буфера, можно, но это сложнее и медленнее; так поступает, например, sort.Stable в Go, и его документация честно предупреждает: O(n log n) сравнений, но O(n log² n) перестановок.

Замер на случайных числах, на Python и Go. Для сравнения — сортировка вставками из статьи о простых сортировках и встроенная сортировка.

Наклон у слияния чуть больше единицы — так выглядит n log n на логарифмических осях, у вставок — около двух. Уже на нескольких сотнях элементов слияние обгоняет вставки, а дальше разница растёт как n / log n. На Python встроенная сортировка обходит наше слияние в двадцать с лишним раз: она написана на C и сравнивает числа без интерпретатора. На Go слияние в два десятка строк держится вровень со стандартной slices.Sort: на миллионе чисел разница в пределах четверти.

На маленьких кусках слиянию мешают накладные расходы: вызов функции, срезы, копирование в буфер. Поэтому настоящие реализации доводят рекурсию не до одного элемента, а до кусков из нескольких десятков и сортируют их вставками. Насколько это выгодно, видно по замеру: одно и то же слияние, но куски не длиннее порога сортируются вставками.

Кривая — ложбина. Слева рекурсия слишком глубокая, справа вставки на длинных кусках начинают платить квадратом. На дне выигрыш — около 30 % на Go и вдвое на Python. На Python дно — около 16 элементов, на Go — около 64: у каждого языка своё соотношение цены вызова функции и цены сдвига. Ровно поэтому в Timsort короткие куски сортируются вставками, а sort.Stable в Go начинает со вставок в блоках по 20 элементов.

Устойчивость даром

Правило «при равенстве брать из левой половины» делает сортировку устойчивой без всякой платы. В демо выше землетрясения силой 7,4 после сортировки идут по датам: 05-02, 07-20, 09-13, 10-10 — так же, как стояли на входе. Поэтому там, где устойчивость обязательна, обычно стоит слияние. Python обещает устойчивость sorted и list.sort, и внутри у них Timsort — гибрид слияний и вставок. Java сортирует массивы объектов тоже Timsort, потому что документация обещает устойчивость, а массивы чисел — быстрой сортировкой с двумя опорными элементами: у двух равных чисел нечего различать, и устойчивость там не нужна.

Когда данные не помещаются в память

Слияние читает каждый список подряд, от начала к концу, и пишет результат тоже подряд. Произвольный доступ ему не нужен, и поэтому слиянием сортируют файлы, которые не помещаются в память. Схема внешней сортировки такая: читаем файл кусками размером с память, каждый кусок сортируем и записываем на диск — получаются отсортированные прогоны. Потом прогоны сливаем, сразу много: в куче держим первый элемент каждого прогона, как в задаче о региональных каталогах.

Сто гигабайт при четырёх гигабайтах памяти — это 25 прогонов. Если сливать их попарно, понадобится ⌈log₂ 25⌉ = 5 проходов по всему файлу. Если слить все 25 сразу, хватит одного прохода, а память делится между 25 буферами чтения по 160 мегабайт.

Единица в скобках — первый проход, на котором создаются прогоны. Так работает GNU sort: большие входы он сортирует кусками во временные файлы и сливает их, не больше заданного числа файлов за раз (параметр --batch-size). Так же поступают базы данных: если для ORDER BY не хватает отведённой памяти, PostgreSQL в плане запроса пишет Sort Method: external merge и сколько места на диске ушло.

Тот же порядок действий годится и в памяти: слить соседние элементы в пары, пары в четвёрки и так далее, без рекурсии. Это восходящая сортировка слиянием — турнир из второй сцены, прочитанный сверху вниз. А если не резать массив вслепую, а взять за прогоны уже упорядоченные куски, которые в данных есть сами, получится естественная сортировка слиянием. На этой идее построен Timsort: на почти отсортированных данных прогонов мало, и слияний почти нет.

Самая старая программа о сортировке

В 1945 году Джон фон Нейман работал над проектом EDVAC — одной из первых машин, хранящих программу в памяти. Машина ещё не была построена, а он уже писал для неё программу — и взял задачу сортировки: от руки, на 23 страницах, расписал слияние двух упорядоченных последовательностей — основу сортировки слиянием. В 1970 году Дональд Кнут разобрал эту рукопись в статье «Von Neumann's first computer program» и назвал её самой ранней из сохранившихся программ для машины с хранимой программой.

Пока большие массивы данных жили на магнитных лентах, слияние оставалось главным способом их сортировать: лента умеет только читать подряд, и слиянию больше ничего не нужно. Изрядная часть третьего тома «Искусства программирования» Кнута посвящена именно сортировке на лентах: сколько лент, в каком порядке сливать, как распределять прогоны, чтобы ленты не простаивали.

Задачи

В первой задаче сортировка слиянием нужна не ради порядка, а ради счётчика: по пути она считает пары, стоящие не на своих местах. Во второй — слияние многих лент сразу.