Cортировка слиянием с использованием O(1) дополнительной памяти

Научившись сливать с использованием [math] O(1) [/math] дополнительной памяти и [math] O(n) [/math] операций , оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером [math] 2^i [/math](за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пари, то просто ничего не делаем.

Алгоритм слияние

На вход алгоритм получает массив который состоит из двух отсортированных кусков. На выходе алгоритм возвращает отсортированный массив. Он состоит из нескольких шагов.

Шаг 1

Разобьем наш массив на группы подряд идущих элементов длиной [math] \sqrt{n} [/math]. Остаток трогать не будем. Найдем группу содержащую конец первого отсортированного куска. Поменяем ее с последней. Добавим последнюю группу в остаток.

Количество операций на этом шаге [math] O(n) [/math].

Шаг 2

Возьмем и отсортируем группы по первому элементу(в случае равенства по последнему). Это можно сделать любой квадратичной или более быстрой сортировкой, которая требует дополнительной памяти [math] О(1) [/math], например сортировка выбором. Следует заметить что после сортировки этих групп элементы которые стоять левее заданного и больше его находились в противоположном куске отсортированного массива, также они находятся в пределах одной группы, поэтому количество инверсий для каждого элемента не больше [math] \sqrt{n} [/math].

Так как кусков [math] \sqrt{n} [/math] количество операций на этом шаге [math] O(n) [/math].

Шаг 3

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

Пример : Пусть длины групп = 3 и x1<y1<x2<x3<y3, где первая группа x1,x2,x3 , а вторая y1,y2,y3.

Номер операции	Массив до выполнения операции	Массив после выполнения операции
1	[x1,x2,x3,y1,y2,y3,a1,a2,a3]	[a1,a2,a3,y1,y2,y3,x1,x2,x3]
2	[a1,a2,a3,y1,y2,y3,x1,x2,x3]	[x1,a2,a3,y1,y2,y3,a1,x2,x3]
3	[x1,a2,a3,y1,y2,y3,a1,x2,x3]	[x1,y1,a3,a2,y2,y3,a1,x2,x3]
4	[x1,y1,a3,a2,y2,y3,a1,x2,x3]	[x1,y1,x2,a2,y2,y3,a1,a3,x3]
5	[x1,y1,x2,a2,y2,y3,a1,a3,x3]	[x1,y1,x2,y2,a2,y3,a1,a3,x3]
6	[x1,y1,x2,y2,a2,y3,a1,a3,x3]	[x1,y1,x2,y2,x3,y3,a1,a3,a2]

Потом, аналогично сольем вторую и треть группу и так до последней группы. Так как после второго шага количество инверсий для каждого элемента не больше [math] \sqrt{n} [/math] то ему надо сдвинутся влево не больше чем на [math] \sqrt{n} [/math] элементов, поэтому в конце не учитывая остаток массив будет отсортированный.

Количество групп [math] \sqrt{n} [/math] и каждое слияние работает за [math] О O(\sqrt{n}) [/math] , поэтому количество операций на этом шаге [math] O(n) [/math] .

Шаг 4

Пусть размер остатка s. Начиная с конца разобьем наш массив на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти [math] О(1) [/math] отсортируем подмассив длиной 2s, который находится в конце. На последних s местах будут находится s максимальных элементов. Оставшаяся часть представляет собой массив содержащий две отсортированные части, причем размер второй равен s. По аналогии с шагом 3 сливаем задом на перед группы длиной s.

Количество операций на этом шаге [math] O(n) [/math].

Шаг 5

Отсортируем остаток и первую группу(после новой разметки на группы). Отсортируем последнюю группу. В результате массив будет отсортированным

Количество операций на этом шаге [math] O(n) [/math].

Ссылки и литература

• Д.Е.Кнут - Искусство программирования (том 3) упр 18 к разделу 5.2.4
• Реализация алгоритма на JAVA