Изменения
Нет описания правки
После того, как мы научились сливать с использованием <tex> O(1) </tex> дополнительной памяти и <tex> O(n) </tex> операций , оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером <tex> 2^i </tex>(за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пары, то просто ничего не делаем. Выполняем это для всех i от <tex> 2 </tex> до <tex> \lceil ln(n) \rceil </tex>
==Алгоритм слияние ==
Пример :
Пусть длины групп равны трем и x1<y1tex> x_1<x2y_1<x3x_2<y3x_3<y_3 </tex>, где первая группа x1 <tex> x_1,x2x_2,x3 x_3 </tex> , а вторая y1<tex> y_1,y2y_2,y3y_3.</tex>
{| border="1"
|-
|1
|<tex>[x1x_1,x2x_2,x3x_3,y1y_1,y2y_2,y3y_3,a1a_1,a2a_2,a3a_3]</tex> |<tex>[a1a_1,a2a_2,a3a_3,y1y_1,y2y_2,y3y_3,x1x_1,x2x_2,x3x_3]</tex>
|-
|2
|<tex>[a1a_1,a2a_2,a3a_3,y1y_1,y2y_2,y3y_3,x1x_1,x2x_2,x3x_3]</tex> |<tex>[x1x_1,a2a_2,a3a_3,y1y_1,y2y_2,y3y_3,a1a_1,x2x_2,x3x_3]</tex>
|-
|3
|<tex>[x1x_1,a2a_2,a3a_3,y1y_1,y2y_2,y3y_3,a1a_1,x2x_2,x3x_3]</tex> |<tex>[x1x_1,y1y_1,a3a_3,a2a_2,y2y_2,y3y_3,a1a_1,x2x_2,x3x_3]</tex>
|-
|4
|<tex>[x1x_1,y1y_1,a3a_3,a2a_2,y2y_2,y3y_3,a1a_1,x2x_2,x3x_3]</tex> |<tex>[x1x_1,y1y_1,x2x_2,a2a_2,y2y_2,y3y_3,a1a_1,a3a_3,x3x_3]</tex>
|-
|5
|<tex>[x1x_1,y1y_1,x2x_2,a2a_2,y2y_2,y3y_3,a1a_1,a3a_3,x3x_3]</tex> |<tex>[x1x_1,y1y_1,x2x_2,y2y_2,a2a_2,y3y_3,a1a_1,a3a_3,x3x_3]</tex>
|-
|6
|<tex>[x1x_1,y1y_1,x2x_2,y2y_2,a2a_2,y3y_3,a1a_1,a3a_3,x3x_3]</tex> |<tex>[x1x_1,y1y_1,x2x_2,y2y_2,x3x_3,y3y_3,a1a_1,a3a_3,a2a_2]</tex>
|}
=== Шаг 4 ===
Пусть размер остатка <tex> s</tex>. Начиная с конца, разобьем наш массив на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти <tex> O(1) </tex>, отсортируем подмассив длиной <tex> 2s</tex>, который находится в конце. На последних <tex> s </tex> местах будут находится s максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен <tex> s</tex>. По аналогии с шагом 3 в обратном порядке сливаем группы длиной <tex> s</tex>.
Количество операций на этом шаге <tex> O(n) </tex>.
