АиСД L04 - Рекурсия и сортировка слиянием

О чём лекция

Квадратичные сортировки на миллионе элементов работают часы. Чтобы сделать быстрее, нужны два инструмента. Рекурсия — функция, которая вызывает саму себя. Слияние — склеить два отсортированных массива в один за линейное время. Вместе они дают сортировку слиянием за $O(N\log N)$. В конце — теорема: быстрее $N\log N$ сортировка сравнением не бывает.

Как читать

Доказательства в блоках «Не из лекции» дописаны к конспекту: на лекции их не было. Всё остальное — с доски.

Маршрут

1. Почему $N^2$ мало → Квадратичные сортировки
2. Функция вызывает себя → Рекурсия
3. Слияние и сортировка слиянием → Сортировка слиянием
4. Быстрее нельзя → нижняя оценка сортировки
5. Оценки и память → Асимптотические оценки, Время работы алгоритма

1. Зачем быстрее

BubbleSort, InsertionSort, SelectionSort — $T(N)=O(N^2)$.

$N\sim 10^6\to 10^{12}\text{ операций}\stackrel{:10^8}{\to }10^4\text{ сек}$

$10^4$ секунд — почти три часа.

2. Рекурсия

Рекурсия — вызов в функции самой себя.

Факториал

Вычислить факториал: $n!=1\cdot 2\cdot 3\cdot \dots \cdot n$.

Определение:

• $n=0$: $0!=1$ (аксиома);
• $\forall n\in \mathbb{N}$: $n!=(n-1)!\cdot n$.

Пример: $5!=5\cdot 4!=5\cdot (4\cdot 3\cdot 2\cdot 1)$.

функ. factorial(n)
    если n = 0
        return 1
    return n * factorial(n − 1)

Как раскрывается вызов:

$$\begin{array}{rl}f(n)& =n\cdot f(n-1)=n(n-1)\cdot f(n-2)=n(n-1)(n-2)\cdot f(n-3)=\\ & =\dots =n(n-1)(n-2)\cdot \dots \cdot 1\cdot f(0)=\\ & =n(n-1)\cdot \dots \cdot 1\cdot 1=n!\end{array}$$

$T(N)=O(N)$.

Не из лекции: доказательство по индукции

База: factorial(0) возвращает 1 = 0!.

Переход: пусть factorial(n − 1) возвращает $(n-1)!$. Тогда factorial(n) возвращает $n\cdot (n-1)!=n!$ — ровно по определению.

Рекурсивная функция повторяет рекурсивное определение, поэтому и доказывается она индукцией. Раскрытие $f(n)$ на доске — та же индукция, выписанная целиком.

Не из лекции: время и память

Время. Вызовов $n+1$: от factorial(n) до factorial(0). Каждый делает $O(1)$ работы, не считая вложенного вызова: $T(N)=O(N)$.

Память. Каждый вызов ждёт, пока вернётся следующий, и всё это время хранит свои данные — хотя бы своё n. В самый глубокий момент живы все $n+1$ вызовов сразу. Они лежат на стеке вызовов (call stack), и $M(N)=O(N)$. Цикл res = res * i посчитал бы то же с $M(N)=O(1)$.

Стек небольшой. Проверено на C++ (GCC 16, -O0, стек 8 МБ по умолчанию в Linux): рекурсия глубиной $2\cdot 10^5$ отрабатывает, глубиной $10^6$ — падает с Segmentation fault.

Восходящая и нисходящая рекурсия

Восходящая	Нисходящая
аргумент увеличивается	аргумент уменьшается
пример: $2\cdot f(n+1)$, $f(10)=1$ → $2^k$	пример: $f(n-1)\cdot n$, $f(0)=1$ → $n!$

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

Не из лекции: восходящий пример целиком

$f(n)=2\cdot f(n+1)$, $f(10)=1$. Раскрываем: $f(n)=2\cdot 2\cdot f(n+2)=\dots =2^k\cdot f(n+k)$. До границы $n+k=10$ нужно $k=10-n$ шагов, и $f(n)=2^{10-n}$. Например, $f(7)=2^3=8$.

Граничное условие должно быть достижимо. Для восходящей рекурсии это значит, что начать надо снизу: $f(11)$ полезет в $f(12),f(13),\dots$ и до $f(10)$ никогда не дойдёт. Так же нисходящий factorial(−1) никогда не дойдёт до 0. Бесконечная рекурсия на практике кончается переполнением стека.

Подробнее — Рекурсия.

3. Функция Merge

Два отсортированных массива сливаем воедино, сохраняя отсортированность.

         L                          R
A = [▧|▧|▧|▧|  ──▶  ]      B = [▧|▧|  ──▶  ]
     │  │ └─────────────┐       │
     ▼  ▼               ▼       ▼
C = [▧ ▧ ▧ ▧ ▧ ▧ |            ]
                 id

Указатель L бежит по A, R — по B, в C пишем меньший из A[L] и B[R].

• Вопрос: C.size = A.size + B.size.
• Вопрос: id = L + R — позиция в C равна числу уже взятых элементов.

Алгоритм

функ. Merge(A, B, lenA, lenB, result)
    L = R = 0
    while (L < lenA and R < lenB)
        если A[L] ≤ B[R]                // ≤ — для устойчивости
            result[L + R] = A[L]
            L++
        иначе
            result[L + R] = B[R]
            R++
    while (L < lenA)
        result[L + R] = A[L]
        L++
    while (R < lenB)
        result[L + R] = B[R]
        R++

Примечание на полях к A[L] ≤ B[R]: «[A | B] — для устойчивости». A стоит в исходном массиве левее B, поэтому при равенстве берём из A.

$N=L+R=lenA+lenB$, $T(N)=O(N)$. $M(N)=O(1)$ — A, B, result созданы не нами.

Не из лекции: доказательство правильности

Инвариант: result[0], …, result[L+R−1] — это $L+R$ наименьших элементов A и B, по неубыванию, и каждый из них не больше A[L] и B[R].

• Вначале $L=R=0$, result пуст — верно.
• Первый цикл: A и B отсортированы, поэтому меньший из A[L] и B[R] — наименьший из ещё не взятых. Он не меньше всего, что уже в result, и встаёт в конец — порядок сохранён.
• Когда один массив кончился, остаток другого уже отсортирован и не меньше всего взятого. Два последних цикла переносят его как есть.

Время: каждая итерация любого из трёх циклов увеличивает $L$ или $R$ на 1. Всего итераций ровно $lenA+lenB=N$: $T(N)=\Theta (N)$.

Не из лекции: почему ≤ даёт устойчивость

Внутри A элементы берутся слева направо — их порядок сохраняется, внутри B тоже. Остаётся пара равных $a\in A$, $b\in B$: в исходном массиве $a$ левее. При A[L] ≤ B[R] первым уходит $a$ — порядок сохранён. При < первым ушёл бы $b$, и Merge стал бы неустойчивым.

4. Разговор про память

Обычно A и B — не отдельные массивы, а две соседние части одного:

        left          A ↗          M      B ↗      right
arr = [ ... | ...................... | ............ | ... ]

Две области:

int* A = arr + left     // lenA = M − left
int* B = arr + M        // lenB = right − M

$A\to [left;M)$, $B\to [M;right)$.

На полях справа — маленький рисунок: отрезок с отметками 1 и 2. Смысл по фото не разобрать.

функ. Merge(arr, left, M, right, result)
    // A → [left, M)   B → [M, right)   arr ← result
    L = R = 0
    A = arr + left
    B = arr + M
    while (L < lenA and R < lenB)
        если A[L] ≤ B[R]
            result[L + R] = A[L]
            L++
        иначе
            result[L + R] = B[R]
            R++
    while (L < lenA)
        result[L + R] = A[L]
        L++
    while (R < lenB)
        result[L + R] = B[R]
        R++
    for i = 0 ... (L + R)
        arr[i + left] = result[i]

lenA и lenB в этой версии не вычисляются, но следуют из записи выше: $lenA=M-left$, $lenB=right-M$. Последний цикл копирует результат обратно в arr на место обеих частей.

Не из лекции: что такое arr + left

В C++ имя массива ведёт себя как адрес его первого элемента, а arr + left — адрес элемента arr[left]. Поэтому A[L] — это arr[left + L], а B[R] — arr[M + R]. A и B — не копии, а «окна» в тот же массив. Указатели в курсе C++ пока не разбирали.

Не из лекции: почему нужен отдельный result

Писать сразу в arr нельзя. Пусть arr = [3, 1], $A=[3]$, $B=[1]$. Первым берётся B[0] = 1 и пишется на позицию left + 0 — прямо поверх A[0] = 3, которую ещё не прочитали. Тройка потеряна.

В общем случае запись идёт на позицию left + L + R, а непрочитанная часть A — это $[left+L,M)$. Пока A не кончился, взять элемент из B — значит записать его на позицию left + L + R $\ge$ left + L, а при $left+L+R<M$ это непрочитанный элемент A. Уже первый же элемент из B ($R=0$) пишется ровно поверх A[L]. Отсюда буфер — и $M(N)=O(N)$ у сортировки слиянием.

5. Merge Sort: схема

[==============|===============]   ← N           ┐
[======|=======] [======|======]   ← N/2         │
      . . . . . . . . . .          ← N/4         │ k разделений,
[] [] [] . . . . . . . . . []      ← N массивов  ┘ N/2^k = 1, k = log₂N
  ↘↙      ↘↙        . . .                        ┐
 [__]    [__]       . . .                        │ слияние
   ↘     ↙                                       │
 [________]   [________] ...                     │
[==============================]                 ┘

Сначала делим пополам, пока не останутся массивы из одного элемента — таких N. Массив из одного элемента уже отсортирован. Потом сливаем соседние обратно.

Асимптотика: $T(N)=O({\log }_{2}N\cdot N)=O(N\log N)$.

Не из лекции: откуда $N\log N$ — аккуратно

Работа уровня. На одной глубине рекурсии части не пересекаются, их суммарная длина не больше N. Merge части длины $\ell$ стоит $O(\ell )$, значит, все слияния одного уровня вместе — $O(N)$.

Число уровней. Отрезок длины $\ell$ делится на части $\lfloor \ell /2\rfloor$ и $\lceil \ell /2\rceil$. По индукции на глубине $t$ длина любой части не больше $\lceil N/2^t\rceil$ (используется $\lceil \lceil x\rceil /2\rceil =\lceil x/2\rceil$). При $t=\lceil {\log }_{2}N\rceil$ это 1 — деление закончилось. Уровней не больше $\lceil {\log }_{2}N\rceil$, и N не обязано быть степенью двойки.

Вызовы. Дерево рекурсии — двоичное с N листьями, в нём $2N-1$ вызовов, на каждый $O(1)$ работы помимо Merge.

Итого $O(N)\cdot \lceil {\log }_{2}N\rceil +O(N)=O(N\log N)$. Слияние копирует все элементы на любом входе, поэтому это и $\Theta (N\log N)$ — даже на отсортированном массиве.

6. Рекурсивная часть

функ. recursiveMergeSort(arr, left, right, buffer)
    // надо отсортировать arr[left; right)
    если right − left = 1
        return
    M = (right + left) / 2          // M = left + (right − left) / 2
    recursiveMergeSort(arr, left, M, buffer)
    recursiveMergeSort(arr, M, right, buffer)
    Merge(arr, left, M, right, buffer)
    return

MergeSort(arr, N)
    buffer = [ ... ]                // размера N
    recursiveMergeSort(arr, 0, N, buffer)
    delete buffer

Итог: $T(N)=O(N\log N)$, $M(N)=O(N)$, устойчивая — да.

Пустой массив

При $N=0$ вызов recursiveMergeSort(arr, 0, 0, buffer): $right-left=0\ne 1$, $M=0$, и функция снова вызывает себя с теми же $(0,0)$ — бесконечно. Проверено на C++: программа падает с Segmentation fault, переполнив стек. Граничное условие должно быть если right − left ≤ 1.

Не из лекции: доказательство правильности

Сильная индукция по длине $\ell =right-left\ge 1$.

• $\ell =1$: один элемент уже отсортирован, функция ничего не делает.
• $\ell \ge 2$: $M=left+\lfloor \ell /2\rfloor$, и $1\le \lfloor \ell /2\rfloor <\ell$. Обе половины непустые и короче $\ell$ — по предположению индукции рекурсивные вызовы их сортируют. Merge двух отсортированных частей даёт отсортированный отрезок. ∎

Непустота половин важна: если бы одна половина совпала со всем отрезком, рекурсия не продвинулась бы — как в случае $N=0$ выше.

Не из лекции: почему $M(N)=O(N)$ и зачем один buffer

• Буфер на N элементов — $O(N)$.
• Стек: глубина рекурсии $\lceil {\log }_{2}N\rceil +1$ вызовов — $O(\log N)$.

Вместе $O(N)$. Буфер создаётся один раз в обёртке и передаётся во все вызовы: Merge пишет в buffer[0 … right−left) и сразу копирует обратно, так что одному вызову он больше не нужен, и следующий может писать туда же. Создавать буфер в каждом Merge — те же $O(N)$ памяти в моменте, но $O(N)$ выделений памяти, а это медленно.

Не из лекции: устойчивость

Индукцией по длине: половины отсортированы устойчиво, все элементы левой половины в исходном массиве левее правой, а Merge с ≤ при равенстве берёт левый. Прогон на 2000 случайных массивах с повторами подтверждает.

Не из лекции: детали для C++

• Середина left + (right − left) / 2, как записано в комментарии на доске, а не (right + left) / 2: сумма может переполнить int. Та же причина, что в бинарном поиске.
• delete buffer с доски: массив, созданный через new[], в C++ освобождают через delete[], а не delete.

7. Теорема о сортировках сравнением

Теорема. Никакая сортировка сравнением не работает быстрее $\Omega (N\log N)$.

На доске доказательство начато и брошено: «Д… ☹».

Сравнение на $N=10^6$:

$$\begin{array}{rl}{N}^2& :10^{12}\stackrel{:10^8}{\to }10^4\text{ сек}\\ N\log N& :10^6\cdot \log 10^6\approx 6\cdot 10^6\cdot 3\approx 20\cdot 10^6=2\cdot 10^7\stackrel{:10^8}{\to }\frac{2}{10}=0,2\text{ сек}\end{array}$$

Логарифм двоичный: ${\log }_{2}10^6=6{\log }_{2}10\approx 6\cdot 3,3\approx 20$.

Не из лекции: доказательство

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

Запустим её на N разных элементах и нарисуем работу как двоичное дерево: узел — сравнение, две ветки — два исхода, лист — конец. Вход проходит путь от корня к листу.

Два входа с разным порядком элементов не могут прийти в один лист: тогда алгоритм получил бы одинаковые ответы на все сравнения и переставил бы оба входа одинаково, а одна перестановка не сортирует два разных порядка. Значит, листьев не меньше $N!$. У дерева высоты $h$ не больше $2^h$ листьев:

$2^h\ge N!\Rightarrow h\ge {\log }_{2}N!\ge {\log }_2{\left(\frac{N}{2}\right)}^{N/2}=\frac{N}{2}{\log }_2\frac{N}{2}.$

Среднее неравенство: в $N!=1\cdot 2\cdots N$ хотя бы $N/2$ множителей не меньше $N/2$. Высота $h$ — число сравнений на худшем входе, и оно $\Omega (N\log N)$. ∎

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

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

Подробнее — Сортировка слиянием, Сортировка.

Грабли

• Рекурсия без достижимого граничного условия — бесконечные вызовы и падение по переполнению стека: factorial(−1), восходящая $f(11)$ при границе $f(10)$.
• Глубокая рекурсия падает даже с правильной базой: стек ограничен. Факториал рекурсией — $O(N)$ памяти, циклом — $O(1)$.
• A[L] < B[R] вместо ≤ — Merge работает, но сортировка теряет устойчивость.
• Слияние прямо в arr без буфера затирает непрочитанные элементы.
• right − left = 1 как база — бесконечная рекурсия на пустом массиве. Нужно ≤ 1.
• (right + left) / 2 в C++ — переполнение на больших индексах.

После этой лекции должно получаться

• написать рекурсивный факториал и доказать его индукцией;
• объяснить, почему рекурсивный факториал занимает $O(N)$ памяти;
• отличать восходящую рекурсию от нисходящей и проверять, что граничное условие достижимо;
• написать Merge, доказать его через инвариант и объяснить, при чём тут ≤;
• объяснить, зачем Merge нужен буфер;
• написать сортировку слиянием и вывести $O(N\log N)$ по уровням;
• доказать, что сортировка сравнением не бывает быстрее $\Omega (N\log N)$.