Изменения

==Алгоритм слияния =={{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 [[Файл:Merge_O(1) </tex> дополнительной памяти. Здесь нам выгодно использовать алгоритм, линейный по числу обменов, т_3.е. подходит [[Сортировка выборомpng|сортировка выбором525px]].

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

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

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

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

[[Файл:Merge_OПопытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И, как в обычном слиянии, пользуясь двумя указателями, сливаем второй блок и только что измененный буфер. Результат начинаем записывать с начала первого блока. Чтобы не потерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректно (1пример использования буфера обмена приведен ниже)_5.png|center|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>, который находится в конце.

[[Файл:Merge_O<tex>S</tex> {{---}} размер остатка вместе с буфером. Используя квадратичную или более быструю сортировку, которая требует <tex> O(1)_6</tex> дополнительной памяти, отсортируем подмассив длиной <tex> 2S </tex>, который находится в конце.png|center|525px]]

Теперь на последних <tex> S </tex> местах будут находиться <tex> S </tex> максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен <tex> S </tex>. По аналогии с тем что делали раньше отсортируем оставшуюся часть, разделив ее на блоки длиной <tex>S</tex>, используя последние <tex>S</tex> как буфер обмена. Не забудем после отсортировать буфер обмена[[Файл:Merge_O(1)_6.png|525px]]

[[Файл:Merge_O(1)_7Теперь на последних <tex> S </tex> местах будут находиться <tex> S </tex> максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен <tex> S </tex>. По аналогии с тем что делали раньше, только в обратную сторону, отсортируем оставшуюся часть, разделив ее на блоки длиной <tex>S</tex>, используя последние <tex>S</tex> как буфер обмена. Не забудем после отсортировать буфер обмена.png|center|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]