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

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

Именно для такой ситуации — и для десятков других, где предсказуемость важнее средней скорости — существует сортировка слиянием (merge sort). Это второй классический пример стратегии «разделяй и властвуй» после быстрой сортировки, но устроен он принципиально иначе: вместо того чтобы тратить силы на хитрое разбиение массива вокруг опорного элемента, merge sort делит массив механически пополам, не глядя на значения элементов, а всю сложную работу переносит на этап объединения уже отсортированных частей.

Это на первый взгляд небольшое отличие в порядке действий даёт совершенно другой набор гарантий. Быстрая сортировка в среднем работает как гоночный болид, но на неудачных данных — уже отсортированном массиве, массиве с одинаковыми ключами, специально подобранной злоумышленником последовательности — она способна деградировать до $O(n^2)$. Сортировка слиянием устроена так, что $O(n\log n)$ гарантировано всегда, вне зависимости от того, как расположены входные данные. За эту гарантию приходится платить — дополнительной памятью и чуть более медленной работой на «удобных» данных в оперативной памяти, — но именно эта надёжность делает merge sort основой продакшен-систем обработки данных, где непредсказуемый всплеск времени выполнения на реальных данных недопустим.

В этом уроке ты разберёшь саму идею деления и слияния, докажешь, почему сложность действительно одинакова в лучшем, среднем и худшем случае, разберёшься, почему алгоритму нужна дополнительная память и что такое устойчивость сортировки, а в конце сравнишь merge sort с быстрой сортировкой по всем ключевым параметрам и увидишь, как ровно эта же идея — разбить, отсортировать по частям, слить — масштабируется до сортировки данных, которые в память вообще не влезают, и до сортировки структур, где привычного доступа «по индексу» попросту нет, как в связном списке.

История

Сортировка слиянием — не просто один из многих алгоритмов сортировки, а, по всей видимости, вообще первый нетривиальный алгоритм, придуманный специально для электронного компьютера. Его автор — Джон фон Нейман, один из главных архитекторов вычислительной техники XX века, в честь которого названа сама «фон-неймановская архитектура» с общей памятью для команд и данных, которую использует практически любой современный компьютер. В 1945 году, работая над проектом EDVAC — одной из первых электронных вычислительных машин с хранимой программой, — фон Нейман написал рукописную заметку, в которой описал именно merge sort: разбить последовательность на части, отсортировать части, слить результат. Эта заметка считается одним из самых ранних сохранившихся описаний программы для компьютера в современном понимании этого слова — задолго до того, как сформировалась сама дисциплина программирования и появился термин «алгоритм» в его нынешнем компьютерном смысле.

Интересно, что мотивация фон Неймана была не столько «придумать быстрый способ сортировки», сколько продемонстрировать саму возможность стройной, рекурсивно организованной программы для новой вычислительной машины. Merge sort оказался удобным полигоном именно потому, что его легко разложить на чёткие, повторяющиеся шаги — раздели, реши для меньшей части, слей обратно, — а это ровно то, что хорошо ложится на архитектуру компьютера с хранимой программой и последовательным выполнением инструкций.

Вторая волна практической славы пришла к merge sort в 1950–60-х годах, когда основным носителем данных для больших вычислений была не оперативная память, а магнитная лента — устройство, которое физически поддерживает только последовательный доступ: чтобы добраться до нужной записи, ленту нужно перемотать, а не «прыгнуть» к произвольному индексу, как в массиве. Быстрая сортировка с её произвольными перестановками элементов вокруг опорного значения для ленты попросту неприменима. А вот merge sort идеально ложится на такую модель доступа: разбиение файла на блоки и последующее слияние — это последовательное чтение и запись, ничего больше. Так сортировка слиянием стала стандартом для «внешней сортировки» данных, которые не помещаются в память целиком, — и остаётся им по сей день, только вместо магнитной ленты сегодня это диски дата-центров и распределённые файловые системы, обслуживающие петабайтные датасеты для обучения моделей.

Идея «разделяй и властвуй» и функция merge

Интуиция

Представь, что тебе нужно упорядочить по алфавиту стопку из тысячи листов с фамилиями. Раздавать всю стопку одному человеку неэффективно. Но если раздать по одному листу тысяче помощников — каждый лист автоматически «отсортирован» сам по себе, ведь один элемент нельзя упорядочить неправильно. Дальше двое соседних помощников берут свои листы и сливают их в стопку из двух отсортированных листов — это тривиально: сравнить два листа и положить меньший сверху. Пары стопок по два снова сливаются в стопки по четыре, четыре — в восемь, и так далее, пока не останется одна полностью отсортированная стопка.

Это и есть вся идея merge sort. Массив рекурсивно делится ровно пополам — не по значениям элементов, а просто по позиции индекса, — до тех пор, пока не останутся подмассивы длиной в один элемент (они автоматически отсортированы, это база рекурсии). Затем начинается обратный процесс: пары отсортированных подмассивов сливаются в бо́льшие отсортированные подмассивы функцией merge, и так до тех пор, пока не соберётся один полностью отсортированный массив исходной длины.

Ключевое отличие от быстрой сортировки: там вся сложная работа делалась до рекурсивных вызовов, на этапе разбиения (partition), а слияние результатов было тривиальным — части уже стояли на своих местах. В merge sort всё наоборот: разбиение тривиально (просто дели индекс пополам), а вся содержательная работа сосредоточена в функции слияния.

Алгоритм

Алгоритм merge sort (рекурсивный):

1. Если длина массива меньше или равна 1 — он уже отсортирован, вернуть его как есть (база рекурсии).
2. Найти середину массива и разделить его на две половины: left и right.
3. Рекурсивно отсортировать left, вызвав merge sort от него.
4. Рекурсивно отсортировать right, вызвав merge sort от него.
5. Слить две уже отсортированные половины left и right в один отсортированный массив функцией merge и вернуть результат.

Функция merge(left, right):

1. Завести пустой результирующий массив result и два указателя i = 0, j = 0 на начала left и right.
2. Пока оба указателя не вышли за границы своих массивов: сравнить left[i] и right[j], меньший из них дописать в result и сдвинуть соответствующий указатель на один шаг вперёд.
3. Как только один из массивов закончился, оставшийся «хвост» другого массива (он уже отсортирован по построению) целиком дописывается в result.
4. Вернуть result.

На Python это записывается почти дословно:

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)


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

Разбор примеров

Пример 1 (лёгкий). Трассировать merge sort на массиве [8, 3, 5, 4].

Фаза деления. [8, 3, 5, 4] делится пополам на [8, 3] и [5, 4]. Каждая из этих пар снова делится пополам: [8, 3] → [8] и [3]; [5, 4] → [5] и [4]. Все подмассивы длины 1 — рекурсия дошла до базового случая.

Фаза слияния, уровень 1. Сливаем [8] и [3]: i=0, j=0, сравниваем 8 и 3, 8 > 3 → берём 3, result=[3]; left исчерпан после i=1? Нет, left=[8] имеет длину 1, i дошёл до 1, left закончился, дописываем хвост right[0:]=[8] → result=[3, 8]. Аналогично сливаем [5] и [4]: 5 > 4 → берём 4, хвост [5] дописываем → result=[4, 5].

Фаза слияния, уровень 2. Сливаем [3, 8] и [4, 5]: i=0,j=0: 3 ≤ 4 → берём 3, result=[3], i=1. i=1,j=0: 8 > 4 → берём 4, result=[3,4], j=1. i=1,j=1: 8 > 5 → берём 5, result=[3,4,5], j=2. right исчерпан, дописываем хвост left[1:]=[8] → result=[3,4,5,8].

Ответ: [3, 4, 5, 8] — итоговый отсортированный массив, получен за 2 уровня деления и 2 уровня слияния.

Пример 2 (средний). Трассировать merge sort на классическом семиэлементном массиве [38, 27, 43, 3, 9, 82, 10] (нечётная длина — важно посмотреть, как алгоритм ведёт себя, когда массив не делится поровну).

Деление. mid = 7 // 2 = 3, значит left = [38, 27, 43], right = [3, 9, 82, 10]. Заметь: половины разной длины (3 и 4) — это нормально, алгоритму не нужно, чтобы они были равны, важно лишь, чтобы каждая была меньше исходного массива.

Дальше [38, 27, 43] делится на [38] и [27, 43], а [27, 43] — на [27] и [43]. Параллельно [3, 9, 82, 10] делится на [3, 9] и [82, 10], а те — на [3], [9] и [82], [10] соответственно. Дно рекурсии — восемь одноэлементных (или уже готовых) подмассивов.

Слияние. [27] и [43] сливаются в [27, 43] (уже так и было). Затем [38] сливается с [27, 43]: 38 > 27 → берём 27; 38 ≤ 43 → берём 38; хвост [43] дописываем → получаем [27, 38, 43].

Параллельно [3] и [9] сливаются в [3, 9]; [82] и [10] сливаются в [10, 82]. Затем [3, 9] и [10, 82] сливаются: 3 ≤ 10 → 3; 9 ≤ 10 → 9; хвост [10, 82] дописываем целиком → [3, 9, 10, 82].

Финальное слияние. [27, 38, 43] и [3, 9, 10, 82]: 27 > 3 → 3; 27 > 9 → 9; 27 > 10 → 10; 27 ≤ 82 → 27; 38 ≤ 82 → 38; 43 ≤ 82 → 43; left исчерпан, дописываем хвост [82].

Ответ: [3, 9, 10, 27, 38, 43, 82].

Пример 3 (важный — демонстрация устойчивости). Отсортировать список кортежей [(5, 'a'), (2, 'b'), (5, 'c'), (2, 'd')] по первому элементу пары функцией merge_sort, сравнивая только первые компоненты.

Деление. [(5,'a'), (2,'b')] и [(5,'c'), (2,'d')], дальше до одиночных элементов.

Слияние левой половины. (5,'a') и (2,'b'): 5 > 2 → сначала (2,'b'), потом хвост (5,'a') → [(2,'b'), (5,'a')].

Слияние правой половины. Аналогично → [(2,'d'), (5,'c')].

Финальное слияние. Сравниваем (2,'b') и (2,'d') — ключи равны (2 = 2)! По условию left[i] <= right[j] при равенстве берётся элемент из левой половины первым: result=[(2,'b')]. Дальше (5,'a') против (2,'d'): 5 > 2 → берём (2,'d'). Остались (5,'a') и (5,'c'): снова равные ключи, снова берём из левой половины первым → (5,'a'), затем хвост (5,'c').

Ответ: [(2,'b'), (2,'d'), (5,'a'), (5,'c')] — обрати внимание, что 'b' стоит перед 'd', а 'a' перед 'c', то есть именно в том порядке, в котором пары с равными ключами шли в исходном массиве. Это и есть устойчивость сортировки, к которой мы ещё вернёмся отдельно.

Почему это важно

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

Гарантированная сложность O(n log n) в любом случае

Интуиция

В быстрой сортировке размер частей после разбиения — лотерея: удачный пивот делит массив пополам, неудачный оставляет один элемент по одну сторону и всё остальное по другую. В merge sort лотереи нет вообще: деление всегда механически пополам, независимо от того, отсортирован массив, обратно отсортирован или заполнен случайными числами. А раз глубина дерева рекурсии фиксирована и не зависит от данных, то и суммарная сложность не может «сорваться» в худшую сторону на неудачном входе — она одинакова всегда.

Алгоритм (доказательство через рекуррентное соотношение)

Теорема (сложность merge sort). Пусть $T(n)$ — время работы сортировки слиянием на массиве длины $n$. Тогда выполняется рекуррентное соотношение

$$T(n) = 2T(n/2) + O(n), \qquad T(1) = O(1)$$

где слагаемое $2T(n/2)$ — это время на рекурсивную сортировку двух половин, а $O(n)$ — время на их слияние функцией merge (каждый элемент из обеих половин ровно один раз попадает в результирующий массив). Решение этого рекуррентного соотношения даёт

$$T(n) = O(n \log n)$$

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

Почему решение именно такое, легче всего увидеть через дерево рекурсии. На верхнем уровне — один вызов на массиве длины $n$, суммарная работа по слиянию на этом уровне (без учёта рекурсивных вызовов) — $O(n)$. На следующем уровне — два вызова на массивах длины $n/2$ каждый, суммарная работа по слиянию на этом уровне — тоже $O(n)$ (два слияния по $n/2$ операций). На уровне ниже — четыре вызова по $n/4$, снова суммарно $O(n)$. Так продолжается, пока размер подмассива не дойдёт до 1 — а поскольку размер каждый раз делится ровно на 2, число уровней дерева равно $\log_2 n$. Итого: $\log_2 n$ уровней, на каждом суммарная работа $O(n)$, значит общая работа — $O(n \log n)$.

Разбор примеров

Пример 1. Массив уже отсортирован: [1, 2, 3, 4, 5, 6, 7, 8]. Многие «наивные» алгоритмы (вставками, пузырьком) на таком входе работают заметно быстрее обычного — почти $O(n)$. Что происходит с merge sort? Деление всё равно пройдёт все $\log_2 8 = 3$ уровня, потому что оно смотрит только на индексы, а не на значения: [1,2,3,4,5,6,7,8] → [1,2,3,4]+[5,6,7,8] → [1,2]+[3,4]+[5,6]+[7,8] → восемь единичных подмассивов. Каждое слияние на обратном пути тоже выполнит полный проход по обеим половинам (хотя в каждом сравнении будет сразу побеждать левый элемент — но само сравнение всё равно происходит). Итог: столько же операций порядка $n \log n$, что и на случайном массиве. Merge sort не умеет использовать «удачность» уже отсортированных данных — и в этом одновременно его слабость (не такой быстрый на удобных данных) и сила (никогда не станет хуже).

Пример 2. Массив отсортирован в обратном порядке: [8, 7, 6, 5, 4, 3, 2, 1]. Это классический пример входа, на котором быстрая сортировка с пивотом «последний элемент» из прошлого урока деградирует до $O(n^2)$ (каждое разбиение отрезает лишь один элемент). Для merge sort ничего похожего не происходит: деление снова пройдёт ровно 3 уровня (никак не зависит от порядка значений), а слияния снова выполнят порядка $n \log n$ сравнений — принципиально столько же, сколько и в примере 1. Ни один вход не способен «обмануть» merge sort и заставить его работать дольше, чем $O(n \log n)$.

Пример 3. Посчитать число уровней рекурсии и оценить число сравнений для массива длины $n = 1000$. Число уровней $\lceil \log_2 1000 \rceil = 10$ (поскольку $2^{10} = 1024 \geq 1000$). На каждом уровне суммарно выполняется не больше $n = 1000$ сравнений при слиянии. Итоговая оценка сравнений — порядка $n \log_2 n \approx 1000 \cdot 10 = 10\,000$, тогда как наивная сортировка пузырьком на том же массиве потребует порядка $n^2 = 1\,000\,000$ сравнений — стократная разница, и она справедлива независимо от того, в каком порядке изначально стояли эти 1000 элементов.

Почему это важно

Для практических систем гарантия «никогда не хуже $O(n\log n)$» — это не абстрактная математическая красота, а конкретное инженерное требование. Если у тебя есть батч-джоб, который должен уложиться в окно обслуживания в 10 минут, алгоритм с непредсказуемым худшим случаем $O(n^2)$ (как quicksort на неудачных данных) может однажды сорвать SLA — например, если во входные логи случайно попадут уже частично отсортированные по времени записи (что для логов совершенно обычная ситуация!). Merge sort такой риск исключает по построению: время выполнения зависит только от размера входа, а не от его содержимого.

Память O(n) и устойчивость сортировки

Интуиция

У быстрой сортировки разбиение выполняется на месте: элементы просто переставляются внутри исходного массива, дополнительная память нужна лишь под стек рекурсивных вызовов, то есть $O(\log n)$ в среднем случае. У merge sort всё иначе: чтобы слить две уже отсортированные половины в правильном порядке, нужно куда-то писать результат по мере сравнения указателей — а сделать это без потери данных прямо поверх исходного массива нельзя, потому что элемент, который ты собираешься перезаписать, ещё может понадобиться для сравнения. Поэтому merge принципиально нуждается во вспомогательном массиве.

Второе важное свойство merge sort — устойчивость. Оно связано не с памятью, а с тем, как именно устроено сравнение внутри функции merge: если правило слияния при равенстве ключей всегда отдаёт предпочтение элементу из левой половины, то относительный порядок «одинаковых» по ключу элементов из исходного массива никогда не нарушается.

Алгоритм (формальные определения)

Требования к памяти. Наивная реализация merge sort через срезы массива (как в коде из первого раздела) на каждом уровне рекурсии создаёт новые списки arr[:mid] и arr[mid:] — операции копирования, которые в сумме по всем уровням рекурсии дают $O(n \log n)$ дополнительной памяти из-за многократного копирования одних и тех же элементов на разных уровнях. Аккуратная реализация, использующая один переиспользуемый буфер размера $n$ и передающая в рекурсию границы [low, high] вместо копий подмассивов, снижает дополнительную память до строго $O(n)$ — независимо от глубины рекурсии.

Устойчивость (stability). Алгоритм сортировки называется устойчивым, если для любых двух элементов исходного массива с одинаковым ключом сравнения их относительный порядок сохраняется и в отсортированном результате. Сортировка слиянием устойчива тогда и только тогда, когда условие сравнения в merge записано как left[i] <= right[j] (нестрогое неравенство): при равенстве ключей элемент из левой половины всегда попадает в результат раньше элемента из правой, а поскольку левая половина в исходном массиве всегда стояла раньше правой, порядок «равных» элементов не нарушается ни на одном уровне рекурсии.

Разбор примеров

Пример 1 (память). Оценить дополнительную память для сортировки массива из миллиона 8-байтных чисел ($n = 10^6$). При аккуратной реализации с одним переиспользуемым буфером нужен ровно один дополнительный массив длины $n$: $10^6 \times 8$ байт $= 8$ МБ сверх исходного массива. При наивной реализации через срезы Python на каждом из $\log_2(10^6) \approx 20$ уровней рекурсии суммарно копируется $n$ элементов, то есть пиковое потребление памяти растёт до порядка $n \log n \approx 2 \times 10^7$ «элементо-копий» за всё время работы (хотя единовременно на стеке лежит меньше — сказывается то, что старые срезы не сразу освобождаются сборщиком мусора). Отсюда практический вывод: для больших данных стоит реализовывать merge sort через индексы и общий буфер, а не через срезы.

Пример 2 (устойчивость помогает многоключевой сортировке). Дан список сотрудников [("Иванов", "IT"), ("Петров", "HR"), ("Сидоров", "IT"), ("Козлов", "HR")], нужно отсортировать сначала по отделу, а внутри отдела — по алфавиту фамилий, причём двумя отдельными проходами сортировки (классический приём многоключевой сортировки). Сначала сортируем устойчивым merge sort по фамилии: [("Козлов","HR"), ("Иванов","IT"), ("Петров","HR"), ("Сидоров","IT")]. Затем сортируем тот же список устойчивым merge sort по отделу — поскольку сортировка устойчива, порядок фамилий внутри каждого отдела, полученный на первом проходе, сохраняется: [("Козлов","HR"), ("Петров","HR"), ("Иванов","IT"), ("Сидоров","IT")] — сначала все HR по алфавиту, затем все IT по алфавиту, ровно то, что требовалось, хотя сортировали мы всего по одному ключу за раз.

Пример 3 (неустойчивость быстрой сортировки). Пусть в merge заменить условие на строгое left[i] < right[j] (без равенства). Возьмём массив пар [(3,'x'), (3,'y')] (уже одноэлементные половины [(3,'x')] и [(3,'y')]). При слиянии: 3 < 3 — ложно (равны!), значит по правилу «иначе» алгоритм возьмёт элемент из правой половины первым → result=[(3,'y')], затем хвост [(3,'x')] → [(3,'y'), (3,'x')]. Порядок перевернулся, хотя в исходном массиве 'x' шёл раньше 'y'! Этот крошечный пример показывает: устойчивость — не автоматическое свойство merge sort, а прямое следствие одной конкретной детали реализации — нестрогого сравнения <=.

Почему это важно

Цена $O(n)$ дополнительной памяти — это не второстепенная деталь, а прямой компромисс с быстрой сортировкой: там, где окружение сильно ограничено по памяти (встроенные системы, обработка на видеокарте с ограниченной видеопамятью, сортировка признаков прямо во время инференса) не может позволить себе удвоение потребления памяти, in-place quicksort часто предпочтительнее. А устойчивость критична в задачах обработки данных и ML-пайплайнов: сортировка pandas.DataFrame.sort_values() по умолчанию использует устойчивый алгоритм именно для того, чтобы многоключевая сортировка (ORDER BY col1, col2 в SQL или последовательные sort_values) давала предсказуемый, воспроизводимый результат, а не случайную перетасовку строк с одинаковыми значениями ключа.

Сравнение с быстрой сортировкой и применение

Интуиция

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

Сравнение (таблица компромиссов)

Алгоритм (внешняя сортировка и сортировка связного списка)

Внешняя сортировка слиянием (external merge sort) — для данных, не помещающихся в память:

1. Разбить входной файл на блоки (chunks), каждый размером не больше доступной оперативной памяти.
2. Загрузить каждый блок в память по очереди, отсортировать его любым быстрым алгоритмом (например, quicksort — в пределах одного блока данные помещаются в RAM, и его худший случай не критичен), записать отсортированный блок обратно на диск как временный файл.
3. Слить все отсортированные временные файлы за один или несколько проходов k-way merge: держать в памяти только по одному «текущему» элементу из каждого из $k$ файлов (через min-heap размера $k$), на каждом шаге выбирать минимальный, записывать его в выходной файл и подгружать следующий элемент из того же файла — точно тот же принцип, что и в обычном двухпутевом merge, только для $k$ источников сразу, и при этом ни один файл целиком в память не загружается.

Сортировка связного списка merge sort'ом:

1. Найти середину списка техникой «медленный/быстрый указатель» (slow/fast pointer): один указатель идёт на один узел за шаг, другой — на два, когда быстрый доходит до конца, медленный стоит ровно на середине. Индексы и произвольный доступ здесь не нужны — только последовательный обход, что идеально ложится на структуру связного списка.
2. Разорвать список на две половины по найденной середине и рекурсивно отсортировать каждую.
3. Слить две отсортированные половины, просто перелинковывая указатели next узлов в нужном порядке — без выделения нового массива под данные, потому что «слияние» — это просто пересборка ссылок.

Разбор примеров

Пример 1 (сортировка связного списка). Дан связный список 4 → 2 → 1 → 3. Найдём середину: медленный указатель стартует на 4, быстрый — тоже на 4; шаг 1: медленный на 2, быстрый на 1; шаг 2: медленный на 1, быстрый вышел за пределы (после 3) — стоп. Середина — узел 1, разрываем список на 4 → 2 и 1 → 3. Рекурсивно: 4 → 2 делится на 4 и 2, сливаются в 2 → 4; 1 → 3 уже упорядочен, но пройдёт тот же путь и даст 1 → 3. Финальное слияние 2 → 4 и 1 → 3: сравниваем головы 2 и 1, 1 меньше → берём 1, следующий сравниваем 2 и 3 → берём 2, дальше 4 и 3 → берём 3, хвост 4 дописываем. Результат: 1 → 2 → 3 → 4, и ни на одном шаге не понадобился доступ по индексу — только переходы по next.

Пример 2 (внешняя сортировка, два блока). Файл из восьми чисел [9, 2, 7, 4, 1, 8, 3, 6], но в памяти помещается только 4 числа за раз. Делим на два блока по 4: [9, 2, 7, 4] и [1, 8, 3, 6]. Сортируем каждый блок в памяти (например, quicksort'ом) и пишем на диск как временные файлы: chunk1 = [2, 4, 7, 9], chunk2 = [1, 3, 6, 8]. Теперь сливаем их точно так же, как в обычном двухпутевом merge, читая по одному числу с головы каждого временного файла: 1 ≤ 2 → пишем 1 (из chunk2); 2 ≤ 3 → пишем 2 (из chunk1); 3 ≤ 4 → пишем 3; 4 ≤ 6 → пишем 4; 6 ≤ 7 → пишем 6; 7 ≤ 8 → пишем 7; 8 ≤ 9 → пишем 8; хвост [9] дописываем. Результат на диске: [1, 2, 3, 4, 6, 7, 8, 9], при этом в памяти в любой момент времени держалось не больше пары чисел из каждого файла плюс один блок на этапе сортировки — а не весь файл целиком.

Пример 3 (k-way merge, три файла). Три уже отсортированных временных файла: F1 = [3, 9], F2 = [1, 5, 8], F3 = [2, 4]. Через min-heap с тремя «головами» файлов (изначально 3, 1, 2): минимум 1 из F2 → пишем 1, подгружаем следующую голову F2 = 5; теперь головы 3, 5, 2, минимум 2 из F3 → пишем 2, следующая голова F3 = 4; головы 3, 5, 4, минимум 3 из F1 → пишем 3, следующая голова F1 = 9; головы 9, 5, 4, минимум 4 из F3, F3 исчерпан → пишем 4; головы 9, 5, —, минимум 5 из F2 → пишем 5, следующая голова F2 = 8; головы 9, 8, —, минимум 8 → пишем 8, F2 исчерпан; остался только 9 из F1 → дописываем. Результат: [1, 2, 3, 4, 5, 8, 9], слито за один линейный проход с кучей размера всего 3, а не 7.

Почему это важно

Ровно эта схема — «раздели на блоки размера с память, отсортируй каждый локально, слей k-way merge'ом» — лежит в основе того, как СУБД выполняют ORDER BY и GROUP BY на таблицах, которые не помещаются в буфер памяти, как Hadoop MapReduce сортирует промежуточные данные на фазе перемешивания (shuffle) между map и reduce, и как Spark реализует sort-merge join при соединении двух огромных датасетов по ключу. Для инженерии данных и промышленного ML это не факультативная теория: любой пайплайн, который агрегирует логи, готовит обучающую выборку из терабайтов сырых данных или сортирует признаки для оконных операций во времени, рано или поздно упирается именно в эту задачу — сортировку данных, которые физически не помещаются в оперативную память одной машины, — и решается она идеями merge sort, а не быстрой сортировки.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Слить вручную два отсортированных массива [1, 4, 6] и [2, 3, 5, 8], используя технику двух указателей.

Задание 2: Сколько уровней рекурсии потребуется merge sort для массива из 16 элементов?

Задание 3: Почему merge sort работает за $O(n \log n)$ даже на уже отсортированном массиве, в отличие от сортировки вставками, которая на таком входе работает за $O(n)$?

Задание 4: Реализовать функцию merge для массивов [2, 7, 9] и [1, 6, 8, 10].

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

merge([2, 7, 9], [1, 6, 8, 10])

Задание 5: Для массива из $n = 1000$ элементов сравни примерное число операций сортировки пузырьком ($O(n^2)$) и merge sort ($O(n \log n)$).

Задание 6: Модифицировать функцию merge, чтобы сортировка шла по убыванию.

if left[i] >= right[j]:
    result.append(left[i]); i += 1
else:
    result.append(right[j]); j += 1

Задание 7: Оценить дополнительную память для сортировки массива из 1 миллиона 8-байтных чисел при аккуратной реализации с одним буфером.

Задание 8: Объяснить своими словами, почему merge sort устойчив, и привести пример пары элементов, порядок которых сохраняется.

Задание 9: Массив [5, 5, 5, 5] (все элементы одинаковые). Сколько уровней деления и сколько сравнений потребуется?

Задание 10: Дан массив [7] (один элемент). Что вернёт merge_sort([7]) и почему рекурсия сразу остановится?

Средние задания (11–20)

Задание 11: Записать рекуррентное соотношение для времени работы merge sort и объяснить смысл каждого слагаемого.

Задание 12: Массив [1,2,3,4,5,6,7,8] (отсортирован по возрастанию). Пройдёт ли merge sort столько же уровней рекурсии, сколько на случайном массиве той же длины? Обосновать.

Задание 13: Массив [8,7,6,5,4,3,2,1] (обратный порядок) — классический худший случай для quicksort с пивотом «последний элемент». Что произойдёт при сортировке этим же массивом через merge sort?

Задание 14: Для массива длины $n=1\,000\,000$ оценить число уровней рекурсии и примерное число сравнений при слиянии.

Задание 15: Почему наивная реализация merge sort через срезы Python (arr[:mid], arr[mid:]) тратит больше памяти, чем реализация с одним переиспользуемым буфером?

Задание 16: Дан список пар [("Смирнов","отдел А"), ("Попов","отдел Б"), ("Волков","отдел А")]. Сначала отсортировать устойчивым merge sort по фамилии, затем — устойчивым merge sort по отделу. Что получится и почему такой порядок проходов даёт правильный многоключевой результат?

Задание 17: Что произойдёт с устойчивостью, если в merge заменить left[i] <= right[j] на left[i] < right[j]? Привести контрпример.

Задание 18: Заполнить таблицу сравнения: указать для quicksort и merge sort худшее время и требуемую дополнительную память.

Задание 19: Почему стандартный partition-based quicksort из прошлого урока обычно неустойчив, а merge sort — устойчив по построению (при правильном условии сравнения)?

Задание 20: Массив [9, 2, 7, 4, 1, 8, 3, 6] требуется отсортировать, но в памяти помещается лишь 4 элемента одновременно. Расписать план действий (без полной трассировки).

Продвинутые задания (21–30)

Задание 21: Реализовать итеративную (bottom-up, без рекурсии) версию merge sort.

def merge_sort_iterative(arr):
    n = len(arr)
    width = 1
    arr = arr[:]
    while width < n:
        for i in range(0, n, 2 * width):
            left = arr[i:i + width]
            right = arr[i + width:i + 2 * width]
            arr[i:i + len(left) + len(right)] = merge(left, right)
        width *= 2
    return arr

Задание 22: Реализовать подсчёт инверсий массива (пар $i a[j]$) модификацией merge sort за $O(n\log n)$.

def count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, inv_left = count_inversions(arr[:mid])
    right, inv_right = count_inversions(arr[mid:])
    merged, inv_split = merge_count(left, right)
    return merged, inv_left + inv_right + inv_split

def merge_count(left, right):
    result, i, j, inv = [], 0, 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
            inv += len(left) - i  # все оставшиеся left[i:] больше right[j]
    result.extend(left[i:]); result.extend(right[j:])
    return result, inv

Задание 23: Реализовать сортировку связного списка (упрощённо, в виде Python-списка узлов {value, next}) через merge sort с техникой «медленный/быстрый указатель» для поиска середины.

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

def split_middle(head):
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    return head, mid

def merge_lists(a, b):
    dummy = Node(0)
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a if a else b
    return dummy.next

def merge_sort_list(head):
    if not head or not head.next:
        return head
    left, right = split_middle(head)
    left = merge_sort_list(left)
    right = merge_sort_list(right)
    return merge_lists(left, right)

Задание 24: Три отсортированных временных файла F1=[4,10], F2=[1,2,9], F3=[3,5] нужно слить в один через k-way merge. Расписать порядок выбора элементов.

Задание 25: Почему для k-way merge на практике используют min-heap (приоритетную очередь) размера $k$, а не линейный перебор $k$ голов на каждом шаге?

Задание 26: Объяснить, почему в реальных гибридных реализациях (например, Timsort) для маленьких подмассивов (менее 20–30 элементов) переключаются на сортировку вставками вместо продолжения рекурсии merge sort.

Задание 27: Дан массив [5, 1, 5, 2, 5, 3]. Проследить, что после сортировки merge sort'ом все три пятёрки останутся в том же относительном порядке друг к другу, в каком стояли изначально (устойчивость на более чем двух равных элементах).

Задание 28: Оценить время работы внешней сортировки слиянием для файла в 100 ГБ при доступной памяти 1 ГБ (без учёта дискового I/O, только количество проходов слияния при простом двухпутевом merge).

Задание 29: Почему quicksort принципиально плохо подходит для внешней сортировки данных на диске, а merge sort — хорошо? Дать содержательный ответ, а не просто «так исторически сложилось».

Задание 30: Спроектировать (на уровне псевдокода/плана, без полной реализации) сортировку 500 ГБ лог-файла на машине с 8 ГБ RAM для последующего построения обучающей выборки по временным меткам.

Частые ошибки

Ошибка 1. Забывают, что merge принципиально нуждается в отдельном вспомогательном массиве, и пытаются «слить на месте» поверх исходного массива без буфера.

Как выглядит: попытка записывать результат сравнения прямо в left или в исходный массив по мере сравнения указателей i и j.

Почему возникает: быстрая сортировка приучает к мысли, что «хорошая» сортировка должна быть in-place, и кажется естественным попытаться сэкономить память и здесь.

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

Ошибка 2. Забывают дописать оставшийся «хвост» одного из массивов после того, как цикл сравнения закончился, потому что второй массив уже исчерпан.

Как выглядит: цикл while i < len(left) and j < len(right) написан правильно, но строки result.extend(left[i:]) и result.extend(right[j:]) после него отсутствуют.

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

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

Ошибка 3. Используют строгое сравнение left[i] < right[j] вместо нестрогого <=, случайно теряя устойчивость сортировки.

Как выглядит: код проходит все тесты на корректность порядка чисел, но при сортировке составных ключей (кортежей, записей) относительный порядок элементов с одинаковым ключом сравнения оказывается перевёрнутым.

Почему возникает: для чисел разница между < и <= в этом месте незаметна на глаз — конечный отсортированный массив выглядит одинаково в обоих случаях, если сравнивать только числа, а не пары «ключ + исходная позиция».

Как правильно: если устойчивость важна (а для многоключевой сортировки она важна почти всегда), сознательно использовать <=, отдавая приоритет левой половине при равенстве ключей.

Ошибка 4. Неправильно вычисляют середину массива для больших индексов: mid = (low + high) / 2 вместо mid = low + (high - low) // 2.

Как выглядит: при работе с очень большими массивами (или в языках с фиксированной разрядностью целых чисел) сумма low + high переполняет допустимый диапазон и даёт отрицательное или некорректное значение середины.

Почему возникает: формула «среднее арифметическое» — первое, что приходит в голову, и на небольших индексах она работает без проблем, поэтому ошибка не проявляется в тестах на маленьких данных.

Как правильно: использовать эквивалентную, но защищённую от переполнения формулу low + (high - low) // 2, особенно в реализациях на языках со статической типизацией целых чисел фиксированного размера.

Ошибка 5. Считают, что merge sort «всегда лучше» быстрой сортировки, потому что у него нет плохого худшего случая, и используют его по умолчанию везде.

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

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

Как правильно: для данных, помещающихся в память, где нет жёстких требований к устойчивости и предсказуемости худшего случая, быстрая сортировка на практике часто быстрее за счёт in-place работы и лучшей кэш-локальности; merge sort стоит выбирать осознанно — когда важны гарантия худшего случая, устойчивость, сортировка связных списков или внешняя сортировка данных вне памяти.

Ошибка 6. При реализации внешней сортировки пытаются сначала целиком прочитать весь файл в память «для простоты», сводя на нет саму идею алгоритма.

Как выглядит: код читает весь файл списком, сортирует его одним вызовом sorted(), и вся конструкция с блоками и k-way merge оказывается лишней.

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

Как правильно: с самого начала проектировать этап чтения так, чтобы в памяти никогда не оказывалось больше одного блока фиксированного размера одновременно — иначе вся конструкция внешней сортировки становится бессмысленной.

Главное запомнить

• Merge sort — «разделяй и властвуй»: массив рекурсивно делится ровно пополам по индексу (не по значениям) до одноэлементных подмассивов, а затем пары отсортированных подмассивов сливаются функцией merge в бо́льшие отсортированные подмассивы.

• Функция merge(left, right) объединяет два уже отсортированных массива в один отсортированный за линейное время $O(n)$ с помощью двух указателей.

• Рекуррентное соотношение $T(n) = 2T(n/2) + O(n)$ решается в $T(n) = O(n\log n)$ — и это верно одновременно для лучшего, среднего и худшего случая, в отличие от быстрой сортировки, у которой худший случай $O(n^2)$.

• Гарантия сложности возникает именно из того, что деление всегда идёт ровно пополам по индексу и не зависит от входных данных — дерево рекурсии всегда имеет ровно $\log_2 n$ уровней.

• Merge sort требует $O(n)$ дополнительной памяти для буфера слияния и не является in-place алгоритмом — это прямая цена за гарантию.

• Сортировка слиянием устойчива (stable): элементы с равными ключами сохраняют исходный относительный порядок — при условии, что сравнение в merge записано нестрого (<=).

• Merge sort отлично подходит для сортировки связных списков, поскольку нуждается только в последовательном доступе к данным, тогда как quicksort требует произвольного доступа для разбиения.

• Ровно та же идея масштабируется до внешней сортировки: разбить данные на блоки размера с память, отсортировать каждый блок локально, слить результаты k-way merge'ом, не загружая весь датасет в память целиком.

• Сравнение с быстрой сортировкой — это не вопрос «какой алгоритм лучше», а вопрос компромисса: quicksort быстрее в среднем и экономнее по памяти на данных, помещающихся в RAM; merge sort надёжнее (гарантия худшего случая), устойчивее и незаменим для внешних данных и связных списков.

• Модификация merge — подсчёт числа «перескоков» элементов из правой половины через оставшиеся элементы левой — даёт классический алгоритм подсчёта инверсий массива за $O(n\log n)$.

Связь с темами курса

Что нужно было знать до этого урока

Этот урок напрямую продолжает две предыдущие темы блока алгоритмов: обзорный урок 266 про виды сортировок задал общий язык и критерии сравнения (время, память, устойчивость), а урок 267 про быструю сортировку впервые показал стратегию «разделяй и властвуй» в действии и её главный недостаток — непредсказуемый худший случай $O(n^2)$. Понимание нотации $O(\cdot)$ из урока 251 и базовое знакомство со связными списками из урока 254 также используются здесь напрямую — во втором примере последнего раздела и в задании 23.

Что изучить дальше

Следующий урок 269 разбирает пирамидальную сортировку (heapsort) — третий алгоритм с гарантированной сложностью $O(n\log n)$ в худшем случае, но устроенный принципиально иначе: heapsort работает in-place, не требуя дополнительной памяти, за счёт структуры данных «двоичная куча», но при этом теряет устойчивость. Вместе quicksort, merge sort и heapsort образуют законченный набор компромиссов между временем, памятью и устойчивостью, и этот же треугольник компромиссов снова и снова будет всплывать в курсе — от выбора структур данных для индексов до устройства библиотечных функций сортировки в реальных языках программирования.

Где это нужно в жизни

🤖 ML/AI и инженерия данных. Внешняя сортировка слиянием — основа обработки датасетов, не помещающихся в оперативную память: сортировка логов перед построением временных признаков, подготовка обучающих выборок из терабайтных источников, фаза shuffle в Hadoop MapReduce и sort-merge join в Spark при соединении больших таблиц по ключу — всё это буквально тот же алгоритм, что разобран в этом уроке, только в промышленном масштабе.

🐍 Языки программирования. Timsort — гибрид merge sort и сортировки вставками, придуманный Тимом Петерсом в 2002 году, — используется как сортировка по умолчанию в Python (sorted(), list.sort()) и в Java (для объектов, Arrays.sort для не-примитивных типов) именно из-за гарантированной сложности и устойчивости.

🗄️ Базы данных. Операция ORDER BY в СУБД на больших таблицах, не помещающихся в буфер памяти, реализуется через внешнюю сортировку слиянием; многие СУБД используют устойчивость сортировки, чтобы гарантировать предсказуемый порядок строк с одинаковыми значениями ключа при многоколоночной сортировке.

📊 Аналитика и ранжирование. Подсчёт инверсий через модифицированный merge sort — стандартный способ измерить, насколько два ранжирования (например, предсказанный моделью порядок и эталонный) отличаются друг от друга, что напрямую используется при оценке качества рекомендательных и поисковых систем.

Интересные факты

• Сортировка слиянием — один из самых ранних задокументированных алгоритмов для электронного компьютера: Джон фон Нейман описал его в рукописной заметке 1945 года в рамках проекта EDVAC, задолго до того, как термин «алгоритм» приобрёл современное компьютерное значение, а сам фон Нейман дал имя архитектуре, на которой работает практически любой современный компьютер.

• В 1950–60-х годах merge sort стал промышленным стандартом сортировки данных на магнитной ленте именно потому, что лента поддерживает только последовательный доступ — той же самой причине, по которой сегодня merge sort лежит в основе внешней сортировки на дисках и в распределённых системах.

• Timsort, разработанный Тимом Петерсом в 2002 году специально для Python, — это адаптивный гибрид merge sort и сортировки вставками: он ищет уже упорядоченные «пробеги» (runs) в реальных данных и сливает их, используя merge sort ровно в тех местах, где данные не упорядочены, — алгоритм назван в честь автора и сегодня используется по умолчанию в Python и Java.

• Подсчёт инверсий массива через модифицированный merge sort — классический пример того, как один и тот же алгоритмический каркас «разделяй и властвуй» решает на первый взгляд совершенно другую задачу (не сортировку, а измерение «беспорядка») почти бесплатно, добавив к обычному слиянию всего одну строку с накоплением счётчика.

Лайфхаки

• Пиши и отлаживай функцию merge отдельно от merge_sort, проверяя её на простых парах массивов вручную — почти все баги в реализации сортировки слиянием живут именно в логике слияния, а не в рекурсивном делении.

• Используй нестрогое сравнение <= (а не <) в merge, если тебе важна устойчивость сортировки — это единственная строчка, от которой она зависит, и её легко получить бесплатно, если помнить об этом заранее.

• Для больших массивов в продакшене реализуй merge_sort через индексы [low, high] и один переиспользуемый буфер вместо срезов arr[:mid] — это сокращает дополнительную память с $O(n\log n)$ до строго $O(n)$.

• Для сортировки связных списков используй технику «медленный/быстрый указатель» для поиска середины за один проход — это избавляет от необходимости заранее знать длину списка и не требует произвольного доступа к элементам.

• Если стоит задача не просто отсортировать, а измерить «степень беспорядка» массива или сравнить два ранжирования — вспомни про подсчёт инверсий: почти всегда это модификация merge sort с одной дополнительной строкой в функции слияния, а не отдельный алгоритм с нуля.

• Для работы с данными, которые не помещаются в память целиком, сразу думай в терминах «блоки размера с RAM → локальная сортировка → k-way merge», а не пытайся искусственно уместить весь датасет в память — это прямой путь к падению процесса по нехватке памяти на реальных объёмах.

• В гибридных реализациях переключайся на сортировку вставками для маленьких подмассивов (обычно менее 20–30 элементов) внутри рекурсии merge sort — асимптотика на таких размерах ничего не решает, а константные накладные расходы на рекурсию и выделение памяти заметно снижаются.

Сортировка слиянием на первый взгляд выглядит скромнее быстрой сортировки — она не побеждает в лобовом сравнении скорости на удобных данных в оперативной памяти, и ей приходится платить лишней памятью за свою надёжность. Но именно эта надёжность — гарантия $O(n\log n)$ без единого исключения, устойчивость и умение работать без произвольного доступа к данным — превращает merge sort из «второго алгоритма в учебнике после quicksort» в рабочую лошадку промышленных систем обработки данных: от сортировки в базах данных и распределённых вычислениях до того, как Python и Java сортируют списки объектов прямо сейчас, пока ты читаешь этот текст. Дальше в курсе, когда ты столкнёшься с обработкой датасетов, не помещающихся в память одной машины, или с необходимостью предсказуемого времени выполнения в продакшен-пайплайне, ты будешь возвращаться именно к этой идее — раздели, реши по частям, слей обратно.