Изменения

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

На вход алгоритм получает массив , который состоит из двух отсортированных кусков. На выходе алгоритм возвращает отсортированный массив. Он Алгоритм состоит из нескольких шагов.

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

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

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

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

Пусть длины групп = 3 равны трем и x1<y1<x2<x3<y3, где первая группа x1,x2,x3 , а вторая y1,y2,y3.

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

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

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

Опять , используя экономную по памяти, хотя и квадратичную , сортировку , отсортируем:

1. #остаток и первую группу. #последнюю группу.

2.последнюю группу. Не стоит забывать , что после новой разметки остаток находится в начале, а не в конце.