Изменения

==Алгоритм слияния =={{boring}}На вход В конспекте содержится несколько ошибок, которые никто не исправлял уже лет 5, половины доказательств нету и вообще это стоит переписать. Если хотите заимплементить корректный алгоритм получает массив, который состоит из двух отсортированных кусковпридется дополнительно подумать головой. Алсо, про "сравнение в реальных условиях" - бред, по времени этот алгоритм в несколько раз медленнее std::sort. ~[[Участник:Yurik|Yurik]]~, 2017

Разобьем наш == Алгоритм ==У нас есть массив на <tex>cnt</tex> подряд идущих блоков длиной <tex>len = \lfloor \sqrt{n} \rfloor </tex>. Остаток трогать не будем. , который состоит из двух отсортированных частей:

[[Файл:Merge_O(1)_2_1.png|center|525px]]

Найдем блок, содержащий конец первого отсортированного куска. Поменяем его с последним блоком. В дальнейшем будем использовать его как буфер обмена.  [[Файл:Merge_O(1)_3.png|center|525px]]  Отсортируем блоки по возрастанию по первому элементу (если первые элементы равны, тогда по последнему). Для этого подойдет любая квадратичная или более быстрая сортировка, которая требует <tex> O (1) </tex> дополнительной памяти. Здесь нам выгодно использовать алгоритм, линейный по числу обменов, т.е. подходит [[Сортировка выбором|сортировка выбором (selection sort)]].  Так как блоков <tex> \sqrt{n} </tex>, то количество операций на этом шаге <tex> O(n) </tex>. [[Файл:Merge_O(1)_4_2.png|center|525px]]

Пользуясь буфером обмена, последовательно сольем пары соседних блоков. В результате мы получим, что первые <tex>len \cdot [[Файл:Merge_O(cnt - 1)</tex> элементов исходного массива отсортированы_3.png|525px]]

[[Файл:Merge_OОтсортируем блоки по возрастанию по первому элементу (1если первые элементы равны, тогда по последнему)_5.png|center|525px]]

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

[[Файл:Merge_O(1)_bufferСледует заметить, что, после сортировки этих блоков, элементы, которые стоят левее заданного и больше его, находились в противоположной части отсортированного массива, также они находятся в пределах одной группы, поэтому количество инверсий для каждого элемента не больше <tex>\sqrt{n}</tex>.png|center|355px]]

=== Шаг 3 ===Попытаемся слить первую Пользуясь буфером обмена, последовательно сольем пары соседних блоков <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> 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> |- Файл:Merge_O(1)_5.png|6 |<tex>[x_1,y_1,x_2,y_2,a_2,y_3,a_1,a_3,x_3525px] </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>len \cdot (cnt - 1)</tex> элементов исходного массива отсортированы. Количество блоков <tex> \sqrt{n} </tex> и каждое слияние работает за <tex> О O(\sqrt{n}) </tex> , массив будет отсортированныйпоэтому количество операций на этом шаге <tex> O(n) </tex>.

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

=== Шаг 4 ===Пусть размер остатка Так как <tex> s S < 2 \sqrt{n}</tex>. Начиная с конца, разобьем наш массив на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти то сортировка пройдет за <tex> O(1n) </tex>, отсортируем подмассив длиной <tex> 2s </tex>, который находится в конце. На последних <tex> s </tex> местах будут находиться s максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен <tex> s </tex>. По аналогии с шагом 3 в обратном порядке сливаем группы длиной <tex> s </tex>.

Количество операций на этом шаге <tex> O[[Файл:Merge_O(n1) </tex>_6.png|525px]]

=== Шаг 5 ===ОпятьТеперь на последних <tex> S </tex> местах будут находиться <tex> S </tex> максимальных элементов. Оставшаяся часть представляет собой массив, используя экономную по памятисодержащий две отсортированные части, хотя и квадратичнуюпричем размер второй равен <tex> S </tex>. По аналогии с тем что делали раньше, сортировкутолько в обратную сторону, отсортируем:оставшуюся часть, разделив ее на блоки длиной <tex>S</tex>, используя последние <tex>S</tex> как буфер обмена. Не забудем после отсортировать буфер обмена.

#остаток и первую группу. #последнюю группу[[Файл:Merge_O(1)_7.png|525px]]

Не стоит забывать, что после новой разметки остаток находится в начале, а не в концеВ результате мы получили отсортированный исходный массив.

Количество операций на этом шаге <tex> O[[Файл:Merge_O(n1) </tex>_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]