Приёмы: снизу вверх, на месте и параллельно

Если ты умеешь развернуть деление пополам в цикл снизу вверх, знаешь, почему буфер заводят один раз, и понимаешь, что даёт независимость подзадач, листай до «Теперь сам».

Как думаешь, зачем разворачивать рекурсию

Сортировка слиянием сверху вниз делит массив пополам, пока не дойдёт до одного элемента, а потом сливает обратно. Но результат-то известен заранее: сначала сливаются пары соседей, потом четвёрки, потом восьмёрки.

Раз порядок известен, зачем вообще спускаться? Можно начать снизу: слить все пары, потом все четвёрки, и так до конца. Тот же алгоритм, та же асимптотика - но ни одного рекурсивного вызова. Вопрос: что мы при этом выигрываем и что теряем?

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

Сборка мебели. Сверху вниз - это читать инструкцию с конца: «чтобы собрать шкаф, соберите каркас; чтобы собрать каркас, соберите боковину». Снизу вверх - разложить все детали и собирать узлами: сначала все боковины, потом каркас, потом шкаф. Результат тот же, но во втором случае не надо держать в голове стек незаконченных дел.

Механизм: четыре приёма

СНИЗУ ВВЕРХ (итеративно)
width = 1
пока width < n:
    слить все соседние куски длины width
    width = width * 2
→ нет рекурсии, нет стека; слияния те же, но в другом порядке

def merge_sort_bottom_up(a):
    n = len(a)
    buf = [0] * n            # ОДИН буфер на весь алгоритм, а не на каждый уровень
    width = 1
    while width < n:
        for lo in range(0, n, 2 * width):
            mid = min(lo + width, n)
            hi = min(lo + 2 * width, n)
            merge(a, buf, lo, mid, hi)
        width *= 2
    return a

merge(a, buf, lo, mid, hi) - та же функция, что и в прошлом уроке: сливает два уже отсортированных куска a[lo:mid] и a[mid:hi] в один, а buf служит ей временным местом. Разница только в том, что буфер передают снаружи, а не выделяют внутри.

НА МЕСТЕ (один буфер)
плохо:  выделять новый список на каждом вызове - это 2n−1 выделений и освобождений
        (одновременно живо O(n), но суммарно через аллокатор проходит O(n·log n))
        и работа сборщика мусора на каждом слиянии
хорошо: один буфер размера n, передаётся вниз по рекурсии

ПАРАЛЛЕЛЬНО
подзадачи независимы ⇒ левую и правую половины можно считать одновременно
объединение - последовательное, поэтому ускорение ограничено им (закон Амдала)

НЕРАВНЫЕ ЧАСТИ
T(n) = T(n/3) + T(2n/3) + n  - главная теорема НЕ применима (части разного размера)
считается деревом: верхние уровни стоят n, нижние меньше (дерево неполное),
              глубина от log₃ n до log_{3/2} n ⇒ Θ(n·log n)

Правило

Четыре приёма поверх схемы. СНИЗУ ВВЕРХ: развернуть рекурсию в цикл по удваивающимся кускам - исчезают стек и вызовы, порядок работы тот же. НА МЕСТЕ: завести один буфер на весь алгоритм и передавать его вниз, иначе памяти уйдёт O(n·log n) вместо O(n). ПАРАЛЛЕЛЬНО: независимые подзадачи считаются одновременно без синхронизации, но ускорение ограничено последовательным объединением. НЕРАВНЫЕ ЧАСТИ: деление не обязано быть пополам, и тогда главная теорема не применима - цену считают деревом рекурсии.

Разбор: сверху вниз против снизу вверх на восьми элементах

Массив [5, 2, 8, 1, 9, 3, 7, 4]. Посмотрим, в каком порядке происходят слияния.

СВЕРХУ ВНИЗ (рекурсия)          СНИЗУ ВВЕРХ (цикл)
спуск: [5,2,8,1] [9,3,7,4]      width = 1:
спуск: [5,2] [8,1]                [5,2]→[2,5]  [8,1]→[1,8]
спуск: [5] [2]                    [9,3]→[3,9]  [7,4]→[4,7]
слияние: [2,5]                  width = 2:
спуск: [8] [1]                    [2,5]+[1,8] → [1,2,5,8]
слияние: [1,8]                    [3,9]+[4,7] → [3,4,7,9]
слияние: [1,2,5,8]              width = 4:
... то же справа ...              [1,2,5,8]+[3,4,7,9] → [1,2,3,4,5,7,8,9]
слияние: [1,2,3,4,5,7,8,9]

Слияния одни и те же, но в РАЗНОМ порядке: рекурсия идёт в глубину и сливает [1,2,5,8] раньше, чем вообще доберётся до правой половины, а цикл идёт по уровням и делает сначала все слияния ширины 1, потом все ширины 2. Результат от порядка не зависит. Рекурсивных вызовов в левом столбце 2n − 1 = 15, в правом ноль; сама merge вызывается одинаково - семь раз на восьми элементах.

Что теряется: рекурсивная версия делит ровно пополам всегда, а итеративная на размере, не кратном степени двойки, сливает куски разной длины (последний обрезан до n). На корректность это не влияет - min(...) в коде выше как раз об этом, - но на самой границе куски получаются неравными, и в бенчмарках разница видна.

Разбор: почему буфер заводят один раз

Сравним две версии слияния по памяти.

буфер на каждом вызове:
    уровень 0: один буфер размера n
    уровень 1: два буфера по n/2   = n
    уровень 2: четыре по n/4       = n
    ...
    живут одновременно только те, что на пути вниз, - но выделяется и
    освобождается 2n−1 кусков, и каждый проходит через сборщик мусора

один буфер:
    n элементов, выделены один раз, дальше только читаются и пишутся

Асимптотика памяти в обоих случаях O(n) - если считать только ОДНОВРЕМЕННО живое. Но цена выделения и освобождения 2n − 1 раз в асимптотике не видна вовсе, а в замере видна отлично: это та же история, что и с порогом из прошлого урока. Общее правило схемы: всё, что можно выделить один раз снаружи рекурсии, надо выделить снаружи.

Отдельная тонкость - не путать «на месте» у сортировки слиянием и у быстрой сортировки. Быстрая сортировка честно работает на месте (O(log n) памяти на стек), а слияние без буфера существует, но его версия медленнее обычной; поэтому в библиотеках стоит слияние С буфером, когда память есть, и быстрая сортировка, когда её нет.

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

Первое: выделять буфер внутри рекурсии - память и сборщик мусора съедят весь выигрыш от n·log n. Второе: в итеративной версии забыть min(lo + 2·width, n) и выйти за границу массива на размерах, не кратных степени двойки. Третье: параллелить слишком мелкие подзадачи: создание потока стоит куда дороже, чем слияние сорока элементов, - параллелить надо ВЕРХНИЕ уровни, а ниже порога считать последовательно. Четвёртое: применять главную теорему к неравному делению: T(n) = T(n/3) + T(2n/3) + n под неё не подходит, хотя ответ у неё тот же n·log n. Пятое: думать, что итеративная версия всегда быстрее: она экономит вызовы, но теряет локальность на верхних уровнях - что именно выиграет, решает замер.

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

Разворачивание рекурсии в цикл - стандартный приём, когда программа падает по глубине стека или когда её переносят на среду, где рекурсия дорога (микроконтроллеры, GPU, SQL-процедуры). Один общий буфер - первое, что делают, когда профайлер показывает время в аллокаторе. А независимость подзадач - причина, по которой деление пополам легло в основу параллельных библиотек: fork/join в Java, rayon в Rust, parallel_for в TBB устроены ровно вокруг этой схемы, потому что для неё не нужны ни блокировки, ни общая изменяемая память. Про ограничение ускорения объединением стоит помнить отдельно: если склейка линейна и последовательна, больше чем в несколько раз ускориться не выйдет, сколько ядер ни дай.

Теперь сам

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

width = 1:  [a0]+[a1]   [a2]+[a3]   [a4]+[a5]          3 слияния
width = 2:  [a0 a1]+[a2 a3]   [a4 a5]+(пусто)          1 слияние (второе вырождено)
width = 4:  [a0..a3]+[a4 a5]                           1 слияние