Сортировка слиянием: разделяй, сортируй, сливай

Если ты умеешь сливать две отсортированные части за Θ(n) двумя указателями и знаешь, почему вся сортировка слиянием - это Θ(n·log n) в любом случае, листай до «Теперь сам».

Как думаешь, как из двух отсортированных списков собрать один

Вот наблюдение, на котором стоит вся глава: слить ДВА уже отсортированных списка в один отсортированный - легко и дёшево. Смотришь на головы обоих, берёшь меньшую, сдвигаешь указатель - и так, пока оба не кончатся. Ни одного лишнего сравнения. А раз слияние дёшево, всю сортировку можно построить на нём: разбей задачу пополам, отсортируй части (тем же способом), слей. Это классическое «разделяй и властвуй» из раздела про рекуррентности - и оно даёт n·log n.

На что это похоже

Две стопки карт, каждая уже разложена по возрастанию рубашкой вниз. Чтобы собрать одну общую стопку, ты смотришь на верхние карты обеих, берёшь меньшую и кладёшь в новую стопку, потом снова сравниваешь верхние. Тебе НЕ надо перебирать стопки целиком - достаточно смотреть на две верхние карты, потому что каждая стопка уже упорядочена. Один проход по обеим стопкам - и общая готова. Это и есть слияние.

Механизм: слить за линию, а рекурсия даст log уровней

Слияние двух отсортированных частей left и right. Заводим два указателя, i в начале left и j в начале right, и пустой результат. Пока обе части не кончились, сравниваем left[i] и right[j], меньший добавляем в результат и сдвигаем его указатель. Когда одна часть кончилась, дописываем хвост другой. Каждый элемент обеих частей берётся ровно раз - слияние стоит Θ(n).

Вся сортировка. merge_sort(массив): если в нём 0 или 1 элемент - он уже отсортирован (база). Иначе делим пополам, рекурсивно сортируем половины и сливаем.

Правило

Сортировка слиянием делит массив пополам, рекурсивно сортирует половины и сливает их за Θ(n) (двумя указателями). Рекуррентность T(n) = 2T(n/2) + n даёт Θ(n·log n) В ЛЮБОМ СЛУЧАЕ - худшего входа у неё нет. Она устойчива, но требует Θ(n) дополнительной памяти под результат слияния. Это гарантированный n·log n ценой лишней памяти.

Разбор: почему это Θ(n·log n)

Это ровно рекуррентность из раздела про главную теорему. Каждый вызов делит массив на две половины (2T(n/2)) и тратит Θ(n) на слияние. По главной теореме (случай 2: f(n) = n совпадает с n^(log₂ 2) = n) ответ Θ(n·log n). Наглядно: дерево рекурсии имеет log₂ n уровней (деление пополam до единицы), и на КАЖДОМ уровне суммарная работа слияний равна n (на верхнем - одно слияние n; на следующем - два по n/2, снова n; и так далее). n работы × log n уровней = Θ(n·log n). Важно: log n уровней получается всегда, независимо от входа, поэтому у сортировки слиянием нет ни плохого, ни хорошего случая - всегда Θ(n·log n).

Разбор: устойчивость и цена памяти

Слияние можно сделать устойчивым: когда left[i] и right[j] РАВНЫ, бери элемент из left (левой, «более ранней» части) - тогда равные сохранят исходный порядок. Это одна строчка (<= вместо < при сравнении), и сортировка слиянием становится устойчивой - важное её достоинство. Плата - память: слияние пишет результат в НОВЫЙ массив, потому что на месте слить две части, не затирая ещё не прочитанное, нельзя без ухищрений. Значит нужен буфер Θ(n). Это отличает её от быстрой сортировки (следующий урок), которая сортирует на месте, но не гарантирует n·log n и не устойчива. Выбор между ними - это выбор «гарантия и устойчивость ценой памяти» против «память и скорость на практике ценой худшего случая».

Что ломается без этого

Первая ошибка - забыть, что слияние требует ДОПОЛНИТЕЛЬНОЙ памяти, и удивляться, почему сортировка слиянием ест Θ(n) сверху: это не баг, а её природа. На больших данных или в условиях жёсткой экономии памяти это может быть решающим против неё. Вторая - сломать базу рекурсии: если не остановиться на массиве из 0 или 1 элемента, рекурсия не завершится. Третья - при слиянии равных брать элемент из ПРАВОЙ части (< вместо <= с приоритетом левой) и молча потерять устойчивость.

Зачем это в работе

Сортировка слиянием - основа устойчивых промышленных сортировок. Timsort (стандартная сортировка объектов в Python и Java) - это по сути умная сортировка слиянием: она ищет уже упорядоченные куски (runs) и сливает их тем же приёмом двух указателей, добавляя адаптивность из прошлой главы. Её выбирают, когда нужна ГАРАНТИЯ n·log n (никаких сюрпризов на плохом входе) и УСТОЙЧИВОСТЬ (сортировка по нескольким ключам - последняя глава раздела). А ещё слияние - единственный простой способ сортировать данные, которые не помещаются в память целиком: их сливают кусками с диска (внешняя сортировка).

Теперь сам

Слей две отсортированные части left = [1, 3, 5] и right = [2, 4] вручную, по шагам. Сколько сравнений понадобится и почему всё слияние - это Θ(n), а не Θ(n²)?