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

В прошлом уроке мы разобрали, как рекурсия разворачивается в стек вызовов и как трассировать глубину до базового случая. В сортировке слиянием глубина рекурсии задаёт число слоёв слияний: на каждом слое суммарно обрабатывается n элементов, поэтому Θ(log n) слоёв дают Θ(n log n) работы.

Шаг разбиения: рекурсивное деление массива до базового случая

Разбиение не перемещает и не сравнивает элементы: оно вычисляет индекс середины и запускает рекурсивные вызовы для двух половин.

def merge_sort(arr: list, lo: int, hi: int) -> None:
    """Сортирует arr[lo:hi] на месте (слияние использует буфер)."""
    if hi - lo <= 1:          # базовый случай: 0 или 1 элемент
        return
    mid = lo + (hi - lo) // 2 # floor((lo+hi)/2), без переполнения
    merge_sort(arr, lo, mid)  # левая часть: размер floor(n/2)
    merge_sort(arr, mid, hi)  # правая часть: размер ceil(n/2)
    merge(arr, lo, mid, hi)   # объединяем две отсортированные половины

Здесь n = hi - lo. Левая часть [lo, mid) содержит ровно (hi - lo) // 2 = ⌊n/2⌋ элементов, правая [mid, hi) — оставшиеся ⌈n/2⌉. При нечётном n правая часть на один элемент длиннее.

Максимальная глубина. Каждый рекурсивный вызов уменьшает размер подзадачи примерно вдвое. Путь от корня до листа (подмассив длины 1) проходит через ⌈log₂ n⌉ делений, а сам лист — это ещё один уровень. Итого максимальная глубина стека для n ≥ 1 равна ⌈log₂ n⌉ + 1. Для n = 4 это 3 уровня: корень → два вызова размера 2 → четыре вызова размера 1.

Важный момент: «глубина» здесь считается как число одновременно активных фреймов на пути от корня до текущего листа, а не общее число всех вызовов. Всего вызовов будет порядка 2n − 1 (бинарное дерево с n листьями), но в стеке одновременно живёт не более ⌈log₂ n⌉ + 1 фреймов.

Операция mid = lo + (hi - lo) // 2 занимает O(1) на вызов. Линейная работа с элементами выполняется не при разбиении, а при последующем слиянии.

Шаг слияния: два указателя, стабильность и стоимость Θ(hi − lo)

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

def merge(arr: list, lo: int, mid: int, hi: int) -> None:
    """Сливает arr[lo:mid] и arr[mid:hi] — обе части уже отсортированы."""
    buf = []
    i, j = lo, mid
    while i < mid and j < hi:
        if arr[i] <= arr[j]:   # <= гарантирует стабильность
            buf.append(arr[i])
            i += 1
        else:
            buf.append(arr[j])
            j += 1
    # дописываем остаток той части, которая не исчерпана
    buf.extend(arr[i:mid])
    buf.extend(arr[j:hi])
    arr[lo:hi] = buf           # копируем результат обратно

Два указателя i и j движутся по левой и правой частям. На каждой итерации цикла один из них продвигается вперёд, поэтому цикл выполнит не более (mid - lo) + (hi - mid) = hi - lo итераций. Хвостовые extend добавляют оставшиеся элементы без сравнений. Итоговое копирование arr[lo:hi] = buf — ещё hi - lo операций. Суммарная стоимость одного слияния: Θ(hi − lo) по времени.

Почему <= обеспечивает стабильность. Стабильность означает, что элементы с одинаковыми ключами сохраняют исходный взаимный порядок. При arr[i] <= arr[j] равный элемент из левой части всегда попадает в буфер раньше равного элемента из правой. Поскольку левая часть в дереве рекурсии соответствует элементам с меньшими исходными индексами, их порядок сохраняется. Замените <= на < — и алгоритм перестанет быть стабильным: при равенстве правый элемент пойдёт первым.

Сколько памяти тратит один merge. Буфер buf в момент слияния имеет размер hi - lo. После копирования результата обратно в arr буфер освобождается — он не живёт дольше своего вызова merge.

Пиковая память всей сортировки определяется самым крупным одновременно живущим буфером. Рекурсивные ветви выполняются последовательно, а не параллельно: сначала полностью завершается левый поддерево, потом правый. Значит, в момент слияния на верхнем уровне (размер буфера n) все буферы вложенных вызовов уже освобождены. Самый большой буфер — финальный, размером n. Глубина стека вызовов — O(log n) фреймов. Итоговая пиковая дополнительная память: O(n) + O(log n) = O(n).

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

Дерево разбиений и слияний для [5, 2, 4, 1]

Для массива [5, 2, 4, 1] можно явно посчитать работу на каждом слое слияний.

Вход: arr = [5, 2, 4, 1], n = 4.

Уровень 0 (корень): один вызов merge_sort([5, 2, 4, 1]). Разбиение даёт [5, 2] и [4, 1].

Уровень 1: два вызова.

• merge_sort([5, 2]) → разбиение на [5] и [2].
• merge_sort([4, 1]) → разбиение на [4] и [1].

Уровень 2 (листья): четыре вызова размера 1 — все мгновенно возвращаются по базовому случаю. Сравнений: 0.

Теперь слияния идут снизу вверх:

Слияние на уровне 1, левое: [5] и [2]. Указатели: 5 > 2, берём 2; левая часть исчерпана, добавляем 5. Итог: [2, 5]. Сравнений: 1.

Слияние на уровне 1, правое: [4] и [1]. 4 > 1, берём 1; добавляем 4. Итог: [1, 4]. Сравнений: 1.

Слияние на уровне 0: [2, 5] и [1, 4].

• 2 > 1 → берём 1, j=1.
• 2 ≤ 4 → берём 2, i=1.
• 5 > 4 → берём 4, j=2, правая исчерпана.
• Дописываем 5.

Итог: [1, 2, 4, 5]. Сравнений: 3.

Сводка по уровням:

Уровень	Слияний	Размеры буферов	Сравнений
2 (листья)	—	—	0
1	2	2 + 2	1 + 1 = 2
0	1	4	3
Итого			5

На уровне 1 суммарный размер буферов 2 + 2 = 4 = n. На уровне 0 — 4 = n. Суммарная работа на каждом уровне пропорциональна n. Уровней всего ⌈log₂ 4⌉ + 1 = 3 (включая листья), активных слияний — 2: уровни 1 и 0. Это согласуется с Θ(log n) слоёв слияний и Θ(n) работы на каждом — Θ(n log n) суммарно.

Пять сравнений — точное число для этого входа. Асимптотическая оценка говорит о росте при увеличении n, а не о точном числе операций на фиксированном примере.

Рекуррентность T(n) = 2T(n/2) + Θ(n) и теорема мастера (случай 2)

Рекуррентность складывается из двух рекурсивных подзадач и линейного слияния.

Составляем рекуррентность. При вызове merge_sort(arr, lo, hi) для подмассива длины n = hi - lo > 1 происходит следующее:

• Два рекурсивных вызова для подмассивов размеров ⌊n/2⌋ и ⌈n/2⌉ — суммарная стоимость T(⌊n/2⌋) + T(⌈n/2⌉).
• Один шаг слияния стоимостью Θ(n).
• Само разбиение (вычисление mid) — O(1), поглощается Θ(n).

Точная рекуррентность: T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + Θ(n), база T(0) = T(1) = Θ(1).

Для асимптотического анализа разницей между ⌊n/2⌋ и ⌈n/2⌉ можно пренебречь, и рекуррентность записывается в стандартной форме:

T(n) = 2T(n/2) + Θ(n)

Важно: стоимость шага слияния Θ(n) не зависит от исходного порядка элементов — указатели всегда проходят по всему подмассиву. Поэтому эта рекуррентность одинакова для лучшего, среднего и худшего случаев.

Теорема мастера, случай 2. Общая форма: T(n) = aT(n/b) + f(n). В нашем случае:

• a = 2 (два рекурсивных вызова),
• b = 2 (каждый для половины),
• f(n) = Θ(n) (стоимость слияния).

Вычисляем критический показатель: log_b a = log₂ 2 = 1, значит n^{log_b a} = n^1 = n.

Условие второго случая: f(n) = Θ(n^{log_b a}), то есть f(n) = Θ(n). Это в точности выполнено.

Заключение теоремы мастера для случая 2:

T(n) = Θ(n^{log_b a} · log n) = Θ(n · log n) = Θ(n log n)

Геометрический смысл: при каждом переходе на следующий уровень дерева рекурсии число подзадач удваивается, но их суммарный размер остаётся n. Это равновесие — f(n) не растёт и не убывает относительно n^{log_b a} — характеризует второй случай. Именно поэтому логарифм появляется как множитель: он считает число уровней, на каждом из которых выполняется Θ(n) работы.

Если бы стоимость слияния была Θ(n²) — работа на нижних уровнях доминировала бы, и мы попали бы в третий случай. Если бы слияние стоило O(1) — доминировала бы рекурсия, первый случай. Merge sort попадает ровно в середину.