234
правки
Изменения
Нет описания правки
На вход алгоритм получает массив, который состоит из двух отсортированных частей. Нам необходимо за <tex>O(1)</tex> дополнительной памяти и <tex>O(n)</tex> времени получить отсортированный массив.<br>
В реализации алгоритм весьма громоздкий. Но сравнение в реальных условиях реализации на C++ (на массивах длиной до <tex>10^8</tex>) показало, что по числу сравнений алгоритм выигрывает у qsort примерно 10%, а по общему времени работы – от <tex>1.2</tex> до <tex>1.3</tex> раз.
== Алгоритм ==
У нас есть массив, который состоит из двух отсортированных частей:
[[Файл:Merge_O(1)_1.png|525px]]
Разобьем наш массив на <tex>cnt</tex> подряд идущих блоков длиной <tex>len = \lfloor \sqrt{n} \rfloor </tex>. Остаток трогать не будем.
[[Файл:Merge_O(1)_2.png|center|525px]]
Найдем блок, содержащий конец первой отсортированной части. Поменяем его с последним блоком. В дальнейшем будем использовать его как буфер обмена.
[[Файл:Merge_O(1)_3.png|center|525px]] Отсортируем блоки по возрастанию по первому элементу (если первые элементы равны, тогда по последнему). Для этого подойдет любая квадратичная или более быстрая сортировка, которая требует <tex> O (1) </tex> дополнительной памяти. Здесь нам выгодно использовать алгоритм, линейный по числу обменов, т.е. подходит [[Сортировка выбором|сортировка выбором]].
[[Файл:Merge_O(1)_4.png|center|525px]]
Для этого подойдет любая квадратичная или более быстрая сортировка, которая требует <tex> O (1) </tex> дополнительной памяти. Для сохранения линейной асимптотики надо использовать алгоритм, линейный по числу обменов, т.е. подходит [[Сортировка выбором|сортировка выбором]]. Так как блоков <tex> \sqrt{n} </tex>, то количество операций на этом шаге <tex> O(n) </tex>.
[[Файл:Merge_O(1)_5.png|525px]]
Так как после предыдущего шага количество инверсий для каждого элемента не больше <tex>S\sqrt{n}</tex> , то ему надо сдвинуться влево не больше, чем на <tex>\sqrt{n}</tex> элементов, поэтому в результате мы получим, что первые <tex>len \cdot (cnt - размер остатка1)</tex> элементов исходного массива отсортированы. Используя квадратичную или более быструю сортировку, которая требует Количество блоков <tex> \sqrt{n} </tex> и каждое слияние работает за <tex> О O(1\sqrt{n}) </tex> дополнительной памяти, отсортируем подмассив длиной поэтому количество операций на этом шаге <tex> 2S O(n) </tex>, который находится в конце.
Так как <tex>S < 2 \sqrt{n}</tex>, то сортировка пройдет за <tex>O(n)</tex>.
[[Файл:Merge_O(1)_7.png|525px]]
В результате мы получили отсортированный исходный массив.
== Использование Пример использования буфера обмена ==Попытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И, как в обычном слиянии, пользуясь двумя указателями, сливаем вторую группу и только что измененный буфер. Результат начинаем записывать с начала первой группы. Чтобы не потерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректно.
[[Файл:Merge_O(1)_buffer.png|center|355px]]
== Ссылки и литература Источники информации ==*[http://habrahabr.ru/post/138146/ Habrahabr {{---}}Сортировка слиянием без использования дополнительной памяти ]*[http://e-maxx.ru/bookz/files/knuth_3.djvu Д.Е.Кнут {{- --}} Искусство программирования (том 3) упр 18 к разделу 5.2.4]*[http://pastebin.com/hN2SnEfP PASTEBIN {{---}} Реализация алгоритма на JAVA]*[http://habrahabr.ru/post/138146/ Сортировка слиянием без использования дополнительной памяти]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]