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