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