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

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

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

Пример работы алгоритма слияния

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

Шаг 1

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

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

Шаг 2

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

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

Шаг 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] O(1) [/math], отсортируем подмассив длиной 2s, который находится в конце. На последних s местах будут находится s максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен s. По аналогии с шагом 3 в обратном порядке сливаем группы длиной s.

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

Шаг 5

Опять, используя экономную по памяти, хотя и квадратичную, сортировку, отсортируем:

1. остаток и первую группу.
2. последнюю группу.

Не стоит забывать, что после новой разметки остаток находится в начале, а не в конце.

В результате массив будет отсортированным

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

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

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