Изменения

==Алгоритм слияния =={{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_2.png|center|525px]] 

Отсортируем блоки по возрастанию по первому элементу (если первые элементы равныНайдем блок, тогда по последнему)содержащий конец первой отсортированной части. Для этого подойдет любая квадратичная или более быстрая сортировка, которая требует <tex> O (1) </tex> дополнительной памятиПоменяем его с последним блоком. Здесь нам выгодно В дальнейшем будем использовать алгоритм, линейный по числу обменов, т.е. подходит [[Сортировка выбором|сортировка выбором]]его как буфер обмена.

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

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

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

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

Пользуясь буфером обмена, последовательно сольем пары соседних блоков <tex>([0, ~ len - 1]</tex> и <tex>[len, ~ 2 ~ len - 1],</tex> потом <tex>[Файл:Merge_O(len, ~ 2 ~ len - 1]</tex> и <tex>[2 ~ len, ~ 3 ~ len - 1],</tex> и т.д.<tex>)_5</tex>.png|center|525px]]

== Использование буфера обмена ==Попытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И, как в обычном слиянии, пользуясь двумя указателями, сливаем вторую группу и только что измененный буфер. Результат начинаем записывать с начала первой группы. Чтобы не потерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину, и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректно[[Файл:Merge_O(1)_5.png|525px]]

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

=== Шаг 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]