Изменения

На вход алгоритм получает массив, который состоит из двух отсортированных частей:

Разобьем наш массив на <tex>cnt</tex> подряд идущих блоков длиной <tex>len = \lfloor \sqrt{n} \rfloor </tex>. Остаток трогать не будем.

Найдем блок, содержащий конец первой отсортированной части. Поменяем его с последним блоком. В дальнейшем будем использовать его как буфер обмена.

Так как блоков <tex> \sqrt{n} </tex>, то количество операций на этом шаге <tex> O(n) </tex>.

Количество блоков <tex> \sqrt{n} </tex> и каждое слияние работает за <tex> О O(\sqrt{n}) </tex> , поэтому количество операций на этом шаге <tex> O(n) </tex>.

Так как <tex>S < 2 \sqrt{n}</tex>, то сортировка пройдет за <tex>O(n)</tex>.

Теперь на последних <tex> S </tex> местах будут находиться <tex> S </tex> максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен <tex> S </tex>. По аналогии с тем что делали раньше, только в обратную сторону, отсортируем оставшуюся часть, разделив ее на блоки длиной <tex>S</tex>, используя последние <tex>S</tex> как буфер обмена. Не забудем после отсортировать буфер обмена.

Попытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И, как в обычном слиянии, пользуясь двумя указателями, сливаем второй блок и только что измененный буфер. Результат начинаем записывать с начала первого блока. Чтобы не потерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректно.

== Ссылки и литература ==