В данной заметке мы поговорим о задаче слияния двух отсортированных массивов с использованием \(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)\) и не требует дополнительной памяти.
Тем самым мы научились решать исходную задачу.