# Inplace merge

В данной заметке мы поговорим о задаче слияния двух отсортированных массивов
с использованием $O(1)$ дополнительной памяти. Данная задача естественно возникает
при попытке сделать сортировку слиянием так, чтобы она не делала никаких аллокаций.

Считается, что читатель знаком с сортировкой слиянием.

**Теорема.** Существует алгоритм, который сливает два подряд идущих отсортированных массива $A, B$,
используя $O(|A| + |B|)$ времени без дополнительной памяти.

Более того, вся дополнительная память будет использована под _счетчики_, числа
размера $O(\log n)$, которыми мы индексируем массив. Далее мы будем пренебрегать
константным количеством оных, то есть фраза _без дополнительной памяти_ значит,
что мы имеем право завести константное число _счетчиков_. Тем самым _дополнительная память_
измеряется элементами массивов.

Мы также считаем, что своп двух элементов также делается _без дополнительной памяти_, в крайнем
случае с помощью $1$, чем мы тоже пренебрегаем.

## Предварительные сведения

**Утверждение.** Циклический сдвиг массива $A$ на любую величину можно сделать за $O(|A|)$ времени и без дополнительной
памяти.

Читателю предлагается попробовать сделать это разными способами, в качестве какого-то из них
предлагается $\text{reverse}(A[0, n)) \circ \text{reverse}(A[k, n)) \circ \text{reverse}(A[0..k))$.

**Лемма 1.** Существует алгоритм, который сливает два подряд идущих массива $A, B$,
используя $O(|A| + |B|)$ времени и $\min(|A|, |B|)$ дополнительной памяти.

**Доказательство.** Исходя из прошлого утверждения мы можем считать, что $A$ -- меньший из массивов
лежит в начале общего буфера. Пусть `a, b` -- указатели на начало $A, B$ соответственно, `c` -- указатель
на начало общего буфера(то есть исходно `c = a`). Скопируем `a` в отдельный буфер `a'`.
Далее сольем `a', b` в `c` как будто бы они не пересекались вовсе.

Заметим, что в процессе работы алгоритма `b - c >= 0`. Действительно, если мы берем очередной элемент из `b`,
то эта разница не меняется, а если из `a`, то уменьшается на $1$, и изначально `b - c = |A|`. Откуда
алгоритм действительно отработает как будто бы буферы не пересекались.

## Основной алгоритм

**Утверждение**. Существует алгоритм, который выделяет $k$ максимальных элементов
из двух подряд идущих отсортированных массивов $A, B$ и передвигает их в конец не меняя относительный порядок остальных,
используя $O(|A| + |B|)$ времени без дополнительной памяти.

Это несложно сделать с помощью циклического сдвига.

**Лемма 2.** Существует алгоритм, который сливает два подряд идущих отсортированных массива $A, B$,
используя $O(|A| + |B| + \min(|A|, |B|)^2)$ времени без дополнительной памяти.

**Доказательство**. Обозначим $k = \min(|A|, |B|)^2$. Выделим $k$ максимумов и переместим их в конец. Пусть
`c = a, b` -- начало $A^\prime, B^\prime$(с вытащенными максимальными элементами) соответственно, `buf` -- указатель на начало максимумов
соответственно. Попробуем слить `a, b` в `c` с помощью буфера `buf` как в Лемме 1. Только теперь нам нельзя присваивать во время слияния,
так как иначе мы потеряем информацию, поэтому будем свапать. Из корректности алгоритма в Лемме 1, мы получаем, что
в начале исходного буфера будет записан результат слияния $A^\prime, B^\prime$. Но так как мы нигде не теряли информацию, в конце также
должны остаться все максимальные элементы, возможно, в каком-то другом порядке. Отсортируем их любой квадратичной сортировкой и получим
требуемое.

Далее обозначим $n = |A| + |B|$ и будем решать исходную задачу.

**Следствие.** Мы научились решать исходную задачу если $\min(|A|, |B|) = O\left( \sqrt{n} \right)$.

Выберем $\beta = \Theta(\sqrt{n})$. Выделим $\beta$ максимальных элементов и переместим их в конец. Это пространство мы будем
использовать как буфер. Далее разобъём $A, B$ на блоки размера $\beta$. В силу Леммы 2 можно считать, что блоки полные.

**Шаг 1.** Итого у нас получилось порядка $\frac{n}{\beta}$ блоков размера $\beta$. Отсортируем их **выбором** по минимальному элементу(при
равенстве сравним еще и по максимальному). Сортировка выбором делает порядка $\left( \frac{n}{\beta} \right)^2$ сравнений и $\frac{n}{\beta}$ свопов.
Стоимость одного сравнения $O(1)$, а свопа $O(\beta)$, поэтому суммарно этот шаг отработает за $O\left( \frac{n^2}{\beta^2} +
\frac{n}{\beta} \beta \right) = O(n)$ в силу выбора $\beta$.

**Лемма 3.** Если отсортировать первые $(t + 1)\beta$ элементов, то на первых $t\beta$ местах будут стоять $t\beta$ минимумов всего
массива.

**Следствие.** Если мы отсортировали первые $(t + 1)\beta$ элементов, то чтобы после этого отсортировать первые $(t + 2)\beta$ достаточно
слить подотрезки $[t\beta, (t + 1)\beta), [(t + 1)\beta, (t + 2)\beta)$.

**Доказательство.** Выделим $t\beta$ минимумов. Все блоки делятся на два типа: из $A$ и из $B$. Рассмотрим последний блок из $A$, в
котором что-то выделено. Утверждается, что в блоках из $A$, которые идут после него не выделено ничего(проверьте!), а если такого нет, то нигде не выделены элементы из $A$. Также выделенные блоки из $B$ после него сразу идут подряд и все, кроме, может быть последнего выделены полностью. Аналогично для блоков из
$B$. Здесь мы как раз пользуемся отсортированностью по минимуму.

Тем самым выделенные элементы должны попасть в первые $(t + 1)$ блоков. Действительно, рассмотрим последний из 'крайних' блоков. Из
структурного утверждения, в каждом блоке до него также что-то выделено.
Пусть до него включительно есть $k$ блоков. Так как частичных блоков не более двух, то хотя бы $k - 2$ заполнены полностью, то есть
выделено хотя бы $(k - 2)\beta + 1$ элементов. Откуда $k \leqslant t + 1$, что и требовалось.

**Шаг 2.** Согласно следствию нам достаточно итеративно сливать соседние блоки. Каждое такое слияние можно выполнить без дополнительной
памяти с помощью буфера из максимумов, которым мы запаслись в начале. Ясно, что суммарно такие слияния работают за $O(n)$.

**Шаг 3.** Квадратично отсортируем буфер из максимумов, и, если требуется, дольем неполные блоки с помощью Леммы 2. Ясно, что эта
процедура работает за $O(n)$ и не требует дополнительной памяти.

Тем самым мы научились решать исходную задачу.

## Полезные ссылки и источники
* [Оригинальная статья Кронрода](https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=34705&option_lang=rus)
* [Лекция Ф.Д.Руховича по алгоритмам и структурам данных](https://www.youtube.com/watch?v=V-kWungDekU&t=4536s)