== Использование буфера обмена ==Попытаемся слить первый и второй блок<tex>S</tex> - размер остатка. Поменяем местами первый блок с буфером обмена. ИИспользуя квадратичную или более быструю сортировку, как в обычном слияниикоторая требует <tex> O(1) </tex> дополнительной памяти, пользуясь двумя указателямиотсортируем подмассив длиной <tex> 2S </tex>, сливаем вторую группу и только что измененный буфер. Результат начинаем записывать с начала первой группы. Чтобы не потерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину, и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректнокоторый находится в конце.
[[Файл:Merge_O(1)_buffer_6.png|center|355px525px]]
=== Шаг 4 ===Пусть размер остатка <tex> s </tex>. Начиная с конца, разобьем наш массив Теперь на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти последних <tex> O(1) S </tex>, отсортируем подмассив длиной <tex> 2s </tex>, который находится в конце. На последних местах будут находиться <tex> s S </tex> местах будут находиться s максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен <tex> s S </tex>. По аналогии с шагом 3 в обратном порядке сливаем группы тем что делали раньше отсортируем оставшуюся часть, разделив ее на блоки длиной <tex> s S</tex>, используя последние <tex>S</tex>как буфер обмена. Не забудем после отсортировать буфер обмена.
Количество операций на этом шаге <tex> O[[Файл:Merge_O(n1) </tex>_7.png|center|525px]]
=== Шаг 5 ===
Опять, используя экономную по памяти, хотя и квадратичную, сортировку, отсортируем:
#остаток и первую группу. #последнюю группуВ результате мы получили отсортированный исходный массив.
Не стоит забывать== Использование буфера обмена ==Попытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И, что после новой разметки остаток находится как в началеобычном слиянии, пользуясь двумя указателями, а сливаем вторую группу и только что измененный буфер. Результат начинаем записывать с начала первой группы. Чтобы не в концепотерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину, и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректно.
В результате массив будет отсортированным Количество операций на этом шаге <tex> O[[Файл:Merge_O(n1) </tex>_buffer.png|center|355px]]
==Ссылки и литература==
*[http://e-maxx.ru/bookz/files/knuth_3.djvu Д.Е.Кнут - Искусство программирования (том 3) упр 18 к разделу 5.2.4]
*[http://pastebin.com/hN2SnEfP Реализация алгоритма на JAVA]
