338
правок
Изменения
Нет описания правки
Разобьем наш массив на блоки <tex>cnt</tex> подряд идущих элементов блоков длиной <tex> len = \lfloor \sqrt{n} \rfloor </tex>. Остаток трогать не будем.
[[Файл:Merge_O(1)_2.png|center|525px]]
Отсортируем блоки по возрастанию по первому элементу (если первые элементы равны, тогда по последнему). Для этого подойдет любая квадратичная или более быстрая сортировка, которая требует дополнительной памяти <tex> O (1) </tex>дополнительной памяти. Здесь нам выгодно использовать алгоритм, линейный по числу обменов, т.е. подходит [[Сортировка выбором|сортировка выбором (selection sort)]].
Так как блоков <tex> \sqrt{n} </tex>, то количество операций на этом шаге <tex> O(n) </tex>.
[[Файл:Merge_O(1)_4.png|center|525px]]
Пользуясь буфером обмена, последовательно сольем пары соседних блоков. В результате мы получим, что первые <tex>len \cdot (cnt - 1)</tex> элементов исходного массива отсортированы.
[[Файл:Merge_O(1)_5.png|center|525px]]
== Использование буфера обмена ==
Попытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И, как в обычном слиянии, пользуясь двумя указателями, сливаем вторую группу и только что измененный буфер. Результат начинаем записывать с начала первой группы. Чтобы не потерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину, и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректно.
[[Файл:Merge_O(1)_buffer.png|center|355px]]
=== Шаг 3 ===
