Изменения

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

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

Потом, аналогично сольем вторую и треть третью группу и так до последней группы. Так как после второго шага количество инверсий для каждого элемента не больше <tex> \sqrt{n} </tex> то ему надо сдвинутся влево не больше чем на <tex> \sqrt{n} </tex> элементов, поэтому в конце не учитывая остаток массив будет отсортированный.

Пусть размер остатка s. Начиная с конца разобьем наш массив на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти <tex> ОO(1) </tex> отсортируем подмассив длиной 2s, который находится в конце. На последних s местах будут находится s максимальных элементов. Оставшаяся часть представляет собой массив содержащий две отсортированные части, причем размер второй равен s. По аналогии с шагом 3 сливаем задом на перед группы длиной s.

Отсортируем Опять используя экономную по памяти, хотя и квадратичную сортировку отсортируем: 1. остаток и первую группу(после новой разметки на группы). Отсортируем 2.последнюю группу.