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] .

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

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