Изменения
→Шаг 3
=== Шаг 3 ===
Попытаемся слить первую и вторую группу. Поменяем местами первую группу и часть остатка. И как в обычном слиянии пользуясь двумя указателями сливаем вторую группу и только что измененную часть остатка. Результат начинаем записывать с начала первой группы. Чтобы ничего не перетерлось вместо записи используем обмен элементов. Так как группы имеют одинаковую длину и между указателем на вторую группу и указателем на запись расстояние равно длине группы, то слияние произойдет корректно.
Пример :
Пусть длины групп = 3 и x1<y1<x2<x3<y3, где первая группа x1,x2,x3 , а вторая y1,y2,y3.
{| border="1"
!Номер операции
!Массив до выполнения операции
!Массив после выполнения операции
|-
|1
|[x1,x2,x3,y1,y2,y3,a1,a2,a3]
|[a1,a2,a3,y1,y2,y3,x1,x2,x3]
|-
|2
|[a1,a2,a3,y1,y2,y3,x1,x2,x3]
|[x1,a2,a3,y1,y2,y3,a1,x2,x3]
|-
|3
|[x1,a2,a3,y1,y2,y3,a1,x2,x3]
|[x1,y1,a3,a2,y2,y3,a1,x2,x3]
|-
|4
|[x1,y1,a3,a2,y2,y3,a1,x2,x3]
|[x1,y1,x2,a2,y2,y3,a1,a3,x3]
|-
|5
|[x1,y1,x2,a2,y2,y3,a1,a3,x3]
|[x1,y1,x2,y2,a2,y3,a1,a3,x3]
|-
|6
|[x1,y1,x2,y2,a2,y3,a1,a3,x3]
|[x1,y1,x2,y2,x3,y3,a1,a3,a2]
=Ссылки и литература=
*[http://e-maxx.ru/bookz/files/knuth_3.djvu| Д.Е.Кнут - Искусство программирования (том 3) упр 18 к разделу 5.2.4]
*[http://pastebin.com/hN2SnEfP Реализация алгоритма на JAVA]
