Изменения

Научившись сливать с использованием <tex> O(1) </tex> дополнительной памяти {{boring}}В конспекте содержится несколько ошибок, которые никто не исправлял уже лет 5, половины доказательств нету и <tex> O(n) </tex> операций вообще это стоит переписать. Если хотите заимплементить корректный алгоритм, оставшееся решение задачи становится очевиднымпридется дополнительно подумать головой. Будем сливать не рекурсивноАлсо, чтобы сэкономить память про "сравнение в стеке. Пусть на iреальных условиях" -том шаге у нас отсортированы подряд идущиебред, не пересекающиеся куски массива размером <tex> 2^i </tex>(за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнегопо времени этот алгоритм в несколько раз медленнее std::sort. Если последнему куску нету пари~[[Участник:Yurik|Yurik]]~, то просто ничего не делаем. 2017

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

Количество операций на этом шаге На вход алгоритм получает массив, который состоит из двух отсортированных частей. Нам необходимо за <tex>O(1)</tex> дополнительной памяти и <tex> O(n) </tex>времени получить отсортированный массив.<br>В реализации алгоритм весьма громоздкий. Но сравнение в реальных условиях реализации на C++ (на массивах длиной до <tex>10^8</tex>) показало, что по числу сравнений алгоритм выигрывает у qsort примерно 10%, а по общему времени работы – от <tex>1.2</tex> до <tex>1.3</tex> раз.

=== Шаг 2 =Алгоритм ==Возьмем и отсортируем группы по первому элементу(в случае равенства по последнему). Это можно сделать любой квадратичной или более быстрой сортировкой которая требует дополнительной памяти не больше чем <tex> О(1) </tex>У нас есть массив, например сортировка выбором. Следует заметить что после сортировки этих групп элементы которые стоять левее заданного и больше его находились в противоположном куске отсортированного массива, также они находятся в пределах одной группы, поэтому количество инверсий для каждого элемента не больше <tex> \sqrt{n} </tex>.который состоит из двух отсортированных частей:

Так как кусков <tex> \sqrt{n} </tex> количество операций на этом шаге <tex> O[[Файл:Merge_O(n1) </tex>_1.png|525px]]

Разобьем наш массив на <tex>cnt</tex> подряд идущих блоков длиной <tex>len === Шаг 3 ===Попытаемся слить первую и вторую группу. Поменяем местами первую группу и часть остатка. И как в обычном слиянии пользуясь двумя указателями сливаем вторую группу и только что измененную часть остатка. Результат начинаем записывать с начала первой группы\lfloor \sqrt{n} \rfloor </tex>. Чтобы ничего Остаток трогать не перетерлось вместо записи используем обмен элементов. Так как группы имеют одинаковую длину и между указателем на вторую группу и указателем на запись расстояние равно длине группы, то слияние произойдет корректнобудем.

Пример [[Файл:Пусть длины групп = 3 и x1<y1<x2<x3<y3, где первая группа x1,x2,x3 , а вторая y1,y2,y3Merge_O(1)_2.png|525px]]

{Найдем блок, содержащий конец первой отсортированной части. Поменяем его с последним блоком. В дальнейшем будем использовать его как буфер обмена.  [[Файл:Merge_O(1)_3.png| border="1" 525px]] !Номер операции !Массив до выполнения операцииОтсортируем блоки по возрастанию по первому элементу (если первые элементы равны, тогда по последнему). !Массив после выполнения операции [[Файл:Merge_O(1)_4.png|-525px]] |1 |[x1Для этого подойдет любая квадратичная или более быстрая сортировка,x2которая требует <tex> O (1) </tex> дополнительной памяти. Для сохранения линейной асимптотики надо использовать алгоритм,x3линейный по числу обменов,y1,y2,y3,a1,a2,a3т.е. подходит [[Сортировка выбором|сортировка выбором]] |[a1. Так как блоков <tex> \sqrt{n} </tex>,a2,a3,y1,y2,y3,x1,x2,x3]то количество операций на этом |-шаге <tex> O(n) </tex>. |2 |[a1Следует заметить,a2что,a3после сортировки этих блоков,y1элементы,y2которые стоят левее заданного и больше его,y3находились в противоположной части отсортированного массива,x1также они находятся в пределах одной группы,x2поэтому количество инверсий для каждого элемента не больше <tex>\sqrt{n}</tex>. Пользуясь буфером обмена,x3] |последовательно сольем пары соседних блоков <tex>([x10,a2,a3,y1,y2,y3,a1,x2,x3~ len - 1] |- |3 |</tex> и <tex>[x1len,a2~ 2 ~ len - 1],a3</tex> потом <tex>[len,y1,y2,y3,a1,x2,x3~ 2 ~ len - 1] |</tex> и <tex>[x12 ~ len,y1~ 3 ~ len - 1],a3</tex> и т.д.<tex>)</tex>. Попытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И,a2как в обычном слиянии,y2пользуясь двумя указателями,y3сливаем второй блок и только что измененный буфер. Результат начинаем записывать с начала первого блока. Чтобы не потерять данные,a1вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину и между указателем на второй блок и указателем на запись расстояние равно длине блока,x2,x3]то слияние произойдет корректно (пример использования буфера обмена приведен ниже).  [[Файл:Merge_O(1)_5.png|-525px]] |4 |[x1Так как после предыдущего шага количество инверсий для каждого элемента не больше <tex>\sqrt{n}</tex>,y1то ему надо сдвинуться влево не больше,a3чем на <tex>\sqrt{n}</tex> элементов,a2поэтому в результате мы получим,y2что первые <tex>len \cdot (cnt - 1)</tex> элементов исходного массива отсортированы. Количество блоков <tex> \sqrt{n} </tex> и каждое слияние работает за <tex> О O(\sqrt{n}) </tex> ,y3поэтому количество операций на этом шаге <tex> O(n) </tex>. <tex>S</tex> {{---}} размер остатка вместе с буфером. Используя квадратичную или более быструю сортировку,a1которая требует <tex> O(1) </tex> дополнительной памяти,x2отсортируем подмассив длиной <tex> 2S </tex>,x3]который находится в конце.  |[x1Так как <tex>S < 2 \sqrt{n}</tex>,y1,x2,a2,y2,y3,a1,a3,x3]то сортировка пройдет за <tex>O(n)</tex>.  [[Файл:Merge_O(1)_6.png|-525px]] |5 |[x1Теперь на последних <tex> S </tex> местах будут находиться <tex> S </tex> максимальных элементов. Оставшаяся часть представляет собой массив,y1содержащий две отсортированные части,x2причем размер второй равен <tex> S </tex>. По аналогии с тем что делали раньше,a2только в обратную сторону,y2отсортируем оставшуюся часть,y3разделив ее на блоки длиной <tex>S</tex>,a1,a3,x3]используя последние <tex>S</tex> как буфер обмена. Не забудем после отсортировать буфер обмена.  [[Файл:Merge_O(1)_7.png|[x1,y1,x2,y2,a2,y3,a1,a3,x3525px]] |- |6В результате мы получили отсортированный исходный массив. == Пример использования буфера обмена ==  [[Файл:Merge_O(1)_buffer.png|[x1,y1,x2,y2,a2,y3,a1,a3,x3355px] |[x1,y1,x2,y2,x3,y3,a1,a3,a2]|}=Ссылки и литература= Источники информации ==*[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] [[Категория: Дискретная математика и алгоритмы]][[Категория: Сортировки]]