Изменения

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

=== Шаг 2 ===

Возьмем и отсортируем группы по первому элементу(в случае равенства по последнему). Это можно сделать любой квадратичной или более быстрой сортировкой которая требует дополнительной памяти не больше чем <tex> О(1) </tex>, например сортировка выбором. Следует заметить что после сортировки этих групп элементы которые стоять левее заданного и больше его с противоположного куска отсортированного массива, также они находятся в пределах одной группы, поэтому количество инверсий для каждого элемента не больше