338
правок
Изменения
м
=== Шаг 3 ===
Попытаемся слить первую и вторую группу. Поменяем местами первую группу и часть остатка. И, как в обычном слиянии, пользуясь двумя указателями, сливаем вторую группу и только что измененную часть остатка. Результат начинаем записывать с начала первой группы. Чтобы ничего не перезаписалось, вместо записи используем обмен элементов. Так как группы имеют одинаковую длину, и между указателем на вторую группу и указателем на запись расстояние равно длине группы, то слияние произойдет корректно.
Пример :
Пусть длины групп равны трем и <tex> x_1<y_1<x_2<x_3<y_3 </tex>, где первая группа <tex> x_1,x_2,x_3 </tex> , а вторая <tex> y_1,y_2,y_3. </tex>
{| border="1"
!Номер операции
!Массив до выполнения операции
!Массив после выполнения операции
|-
|1
|<tex>[x_1,x_2,x_3,y_1,y_2,y_3,a_1,a_2,a_3] </tex>
|<tex>[a_1,a_2,a_3,y_1,y_2,y_3,x_1,x_2,x_3] </tex>
|-
|2
|<tex>[a_1,a_2,a_3,y_1,y_2,y_3,x_1,x_2,x_3] </tex>
|<tex>[x_1,a_2,a_3,y_1,y_2,y_3,a_1,x_2,x_3] </tex>
|-
|3
|<tex>[x_1,a_2,a_3,y_1,y_2,y_3,a_1,x_2,x_3] </tex>
|<tex>[x_1,y_1,a_3,a_2,y_2,y_3,a_1,x_2,x_3] </tex>
|-
|4
|<tex>[x_1,y_1,a_3,a_2,y_2,y_3,a_1,x_2,x_3] </tex>
|<tex>[x_1,y_1,x_2,a_2,y_2,y_3,a_1,a_3,x_3] </tex>
|-
|5
|<tex>[x_1,y_1,x_2,a_2,y_2,y_3,a_1,a_3,x_3] </tex>
|<tex>[x_1,y_1,x_2,y_2,a_2,y_3,a_1,a_3,x_3] </tex>
|-
|6
|<tex>[x_1,y_1,x_2,y_2,a_2,y_3,a_1,a_3,x_3] </tex>
|<tex>[x_1,y_1,x_2,y_2,x_3,y_3,a_1,a_3,a_2] </tex>
|}
Потом аналогично сольем вторую и третью группу и так до последней группы. Так как после второго шага количество инверсий для каждого элемента не больше <tex> \sqrt{n} </tex>, то ему надо сдвинуться влево не больше, чем на <tex> \sqrt{n} </tex> элементов, поэтому в конце, не учитывая остаток, массив будет отсортированный.
Количество групп <tex> \sqrt{n} </tex>, и каждое слияние работает за <tex> О O(\sqrt{n}) </tex> , поэтому количество операций на этом шаге <tex> O(n) </tex> .
Нет описания правки
Отсортируем блоки по возрастанию по первому элементу (если первые элементы равны, тогда по последнему). Для этого подойдет любая квадратичная или более быстрая сортировка, которая требует <tex> O (1) </tex> дополнительной памяти. Здесь нам выгодно использовать алгоритм, линейный по числу обменов, т.е. подходит [[Сортировка выбором|сортировка выбором (selection sort)]].
Так как блоков <tex> \sqrt{n} </tex>, то количество операций на этом шаге <tex> O(n) </tex>.
Пользуясь буфером обмена, последовательно сольем пары соседних блоков. В результате мы получим, что первые <tex>len \cdot (cnt - 1)</tex> элементов исходного массива отсортированы.
Количество групп <tex> \sqrt{n} </tex>, и каждое слияние работает за <tex> О O(\sqrt{n}) </tex> , поэтому количество операций на этом шаге <tex> O(n) </tex>.
[[Файл:Merge_O(1)_5.png|center|525px]]
[[Файл:Merge_O(1)_buffer.png|center|355px]]
=== Шаг 4 ===
