Изменения

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

==Алгоритм слияния ==[[Файл:Freememorymerge.png|right|380px|thumb|Пример работы алгоритма слияния]]На вход алгоритм получает массив, который состоит из двух отсортированных кусков. На выходе алгоритм возвращает отсортированный массив. Алгоритм состоит из нескольких шагов.=== Шаг 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> O (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>. Чтобы ничего Остаток трогать не перезаписалось, вместо записи используем обмен элементов. Так как группы имеют одинаковую длину, и между указателем на вторую группу и указателем на запись расстояние равно длине группы, то слияние произойдет корректнобудем.

Пример [[Файл:Пусть длины групп равны трем и <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_3Merge_O(1)_2. </tex>png|525px]]

{| 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> элементов, поэтому в конце, не учитывая остаток, массив будет отсортированный[[Файл:Merge_O(1)_3.png|525px]]

Количество групп <tex> \sqrt{n} </tex>, и каждое слияние работает за <tex> О OОтсортируем блоки по возрастанию по первому элементу (\sqrt{n}) </tex> если первые элементы равны, поэтому количество операций на этом шаге <tex> O(nтогда по последнему) </tex> .

=== Шаг 4 ===Пусть размер остатка <tex> s </tex>. Начиная с конца, разобьем наш массив на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти <tex> O[[Файл:Merge_O(1) </tex>, отсортируем подмассив длиной <tex> 2s </tex>, который находится в конце. На последних <tex> s </tex> местах будут находится s максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен<tex> s </tex>. По аналогии с шагом 3 в обратном порядке сливаем группы длиной <tex> s </tex>_4. png|525px]]

Количество Для этого подойдет любая квадратичная или более быстрая сортировка, которая требует <tex> O (1) </tex> дополнительной памяти. Для сохранения линейной асимптотики надо использовать алгоритм, линейный по числу обменов, т.е. подходит [[Сортировка выбором|сортировка выбором]]. Так как блоков <tex> \sqrt{n} </tex>, то количество операций на этом шаге <tex> O(n) </tex>.

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

#остаток Пользуясь буфером обмена, последовательно сольем пары соседних блоков <tex>([0, ~ len - 1]</tex> и первую группу<tex>[len, ~ 2 ~ len - 1],</tex> потом <tex>[len, ~ 2 ~ len - 1]</tex> и <tex>[2 ~ len, ~ 3 ~ len - 1],</tex> и т.д. #последнюю группу<tex>)</tex>.

Не стоит забыватьПопытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И, что после новой разметки остаток находится как в началеобычном слиянии, а пользуясь двумя указателями, сливаем второй блок и только что измененный буфер. Результат начинаем записывать с начала первого блока. Чтобы не в концепотерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректно (пример использования буфера обмена приведен ниже).

Так как после предыдущего шага количество инверсий для каждого элемента не больше <tex>\sqrt{n}</tex>, то ему надо сдвинуться влево не больше, чем на <tex>\sqrt{n}</tex> элементов, поэтому в результате мы получим, что первые <tex>len \cdot (cnt - 1)</tex> элементов исходного массива отсортированы. Количество блоков <tex> \sqrt{n} </tex> и каждое слияние работает за <tex> О O(\sqrt{n}) </tex> , поэтому количество операций на этом шаге <tex> O(n) </tex>.

<tex>S</tex> {{---}} размер остатка вместе с буфером. Используя квадратичную или более быструю сортировку, которая требует <tex> O(1) </tex> дополнительной памяти, отсортируем подмассив длиной <tex> 2S </tex>, который находится в конце. Так как <tex>S < 2 \sqrt{n}</tex>, то сортировка пройдет за <tex>O(n)</tex>. [[Файл:Merge_O(1)_6.png|525px]] Теперь на последних <tex> S </tex> местах будут находиться <tex> S </tex> максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен <tex> S </tex>. По аналогии с тем что делали раньше, только в обратную сторону, отсортируем оставшуюся часть, разделив ее на блоки длиной <tex>S</tex>, используя последние <tex>S</tex> как буфер обмена. Не забудем после отсортировать буфер обмена. [[Файл:Merge_O(1)_7.png|525px]] В результате мы получили отсортированный исходный массив. == Пример использования буфера обмена == [[Файл:Merge_O(1)_buffer.png|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] [[Категория: Дискретная математика и алгоритмы]][[Категория: Сортировки]]