Изменения
Нет описания правки
=== Шаг 2 ===
Возьмем и отсортируем группы по первому элементу(в случае равенства по последнему). Это можно сделать любой квадратичной или более быстрой сортировкой , которая требует дополнительной памяти не больше чем <tex> О(1) </tex>, например сортировка выбором. Следует заметить что после сортировки этих групп элементы которые стоять левее заданного и больше его находились в противоположном куске отсортированного массива, также они находятся в пределах одной группы, поэтому количество инверсий для каждого элемента не больше
<tex> \sqrt{n} </tex>.
Количество групп <tex> \sqrt{n} </tex> и каждое слияние работает за <tex> О O(\sqrt{n}) </tex> , поэтому количество операций на этом шаге <tex> O(n) </tex> .
=== Шаг 4 ===
Пусть размер остатка s. Начиная с конца разобьем наш массив на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти <tex> О(1) </tex> отсортируем подмассив длиной 2s, который находится в конце. На последних s местах будут находится s максимальных элементов. Оставшаяся часть представляет собой массив содержащий две отсортированные части, причем размер второй равен s. По аналогии с шагом 3 сливаем задом на перед группы длиной s.
Количество операций на этом шаге <tex> O(n) </tex>.
=== Шаг 5 ===
Отсортируем остаток и первую группу(после новой разметки на группы).
Отсортируем последнюю группу.
В результате массив будет отсортированным
Количество операций на этом шаге <tex> O(n) </tex>.
=Ссылки и литература=
*[http://e-maxx.ru/bookz/files/knuth_3.djvu| Д.Е.Кнут - Искусство программирования (том 3) упр 18 к разделу 5.2.4]
*[http://pastebin.com/hN2SnEfP Реализация алгоритма на JAVA]
