Сортировка методом слияний
Существует еще один метод сортировки элементов массива, эффективность которого сравнительно велика, - метод слияний.
Этот метод состоит в разбиении данного массива на несколько частей, которые сортируются по отдельности и впоследствии “сливаются” в одну.
Пусть массив а [1...n ] разбивается на части длиной k, тогда первая часть - а [ 1 ], а [ 2 ], ...., а [ k ], вторая - а [ k +1 ], а [ k + 2 ], ...., а [ 2k ] и так далее. Если n не делится на k, то в последней части будет менее k элементов.
После того как массивы - части упорядочены, можно объединить их в упорядоченные массивы - части, состоящие не более чем из 2 k элементов, которые далее объединить в упорядоченные массивы длиной не более 4 k, и так далее, пока не получится один упорядоченный массив.
Таким образом, чтобы получить отсортированный массив этим методом, нужно многократно “сливать” два упорядоченных отрезка массива в один упорядоченный отрезок. При этом другие части массива не затрагиваются.
Задача
Дан массив а [ 1...k ] целых чисел и числа k, m, n, такие, что k ≤ m ≤ n. Описать процедуру, которая сливает отрезки массива а [ k + 1 ], ..., а [ m ] и а [ m + 1 ], ,...., а [ n ] в упорядоченный отрезок а [ k + 1 ], ..., а [ n ].
Основная идея решения состоит в сравнении очередных элементов каждой части, выяснении, какой из них меньше, переносе его в массив с, который является вспомогательным, и продвижении по тому массиву - части, из которого взят элемент. Когда одна из частей будет пройдена до конца, остается только перенести в с оставшиеся элементы второй части, сохраняя их порядок.
Рассмотрим пример.
Пусть первая часть ( часть а ) состоит из 5 элементов:
... 3 5 8 11 16 ...,
а вторая часть ( часть b ) - из 8 элементов:
... 1 5 7 9 12 13 18 20 ...
По условию оба массива - части упорядочены. Нужно сформировать массив с, который будет содержать 13 элементов.
Введем обозначения:
i - номер обрабатываемого элемента части а;
j - номер обрабатываемого элемента части b;
g - номер заполняемого массива части с.
Поскольку заполнение массива с ведется с его начала, на первом шаге значение g =1.
1 -й шаг: на первое место в массиве с претендуют а [k + 1] = 3 и
b [ m + 1 ] = 1 ( i = k + 1, j = m + 1 ). Так как 1 < 3, в массив с нужно занести 1 и перейти к следующему элементу части b, то есть увеличить j на 1 (значение j станет равно m + 2 ), а также увеличить на 1 значение g ( значение g будет равно 2 ).
2 -й шаг: теперь нужно сравнить а [ k + 1 ] = 3 и b [ m + 2 ] = 5 . 3 < 5, следовательно, на второе место в с надо занести а [ k + 1 ] = 3. Затем нужно увеличить на одно значение i и g.
3 -й шаг: на третье место массива с претендуют два одинаковых элемента - а [ k + 2 ] = 5 и b [ m + 2 ] = 5. В этом и подобных случаях договоримся заносить в с первым элемент из части а. Таким образом, с [ 3 ] = а [ k + 2 ], а значение
g = 4, i = k + 3, j остается равным m + 2.
4-11 - й шаги: рассуждая аналогичным образом, нужно занести в с элементы 5, 7, 8, 9, 11, 12, 13, 16.
После выполнения 11 - го шага первая часть будет занесена в с полностью, значение g равно m + 7, значение g = 12.
12 - й шаг: так как часть а закончилась, а “хвост” части b упорядочен по условию, то двенадцатым элементом массива с будет первый элемент “хвоста” b, то есть b [ m + 7 ] = 18.
13 -й шаг: последним элементом массива с будет последний элемент b – 20.
На рисунке схематично изображен процесс заполнения массива c.
часть a
... 3 5 8 11 16 ...
 | | |  |  |
шаг 2 шаг 3 шаг 6 шаг 8 шаг 11
3>6 5=5 8<9 11<12 16<19
 |  |  |
C
       1
|
 |  |
шаг 1 шаг 4 шаг 5 шаг 7 шаг 9 шаг 10 шаг 12
1<3 5<8 7<8 9<11 12<16 13<16
 | |||||||
 |  |  |
... часть b
Сейчас можем описать процедуру слияния двух упорядоченных массивов размерностей m-k и n-m соответственно в третий упорядоченный массив, размерности n-k.
Procedure sorting4(k,m,n:integer);
var i,j:integer;
begin
i:=k+1;
j:=m+1;
k:=1;
while (i<=m) and (j<=n) do
{пока не закончилась хотя бы одна часть}
begin
if a[i]<=b[j] then
begin c[k]:=a[i]; inc(i); end
else begin c[k]:=b[j]; inc(j); end;
inc(k);
end;
{один из массивов - частей обработан полностью}
{осталось перенести в с остаток другого массива - части}
while i<=m do
begin c[k]:=a[i]; inc(i); inc(k); end;
while j<=n do
begin c[k]:=b[j]; inc(j); inc(k); end;
end;
Приведем пример программы, использующий эту процедуру в некоторой переработке ( вместо a[k+1], ..., a[m] используем a[1..k], а вместо a[m+1], ..., a[n] используем b[1..m], где k+m = n ). Эта программа делит исходный массив на две части, затем каждая часть сортируется методом “пузырьковой” сортировки, после чего части соединяются с помощью данной процедуры в искомый массив. Очевидно, скорость такого метода выше, чем просто использование “пузырьковой ” сортировки.
program n4;
const n=5;
type ar=array[1..n] of integer;
var k,m,i:integer;
a,b,c:ar;
Procedure sorting4;
var s,i,j:integer;
begin
i:=1;
j:=1;
s:=1;
while (i<=k) and (j<=m) do
{пока не закончилась хотя бы одна часть}
begin
if a[i]<=b[i] then
begin c[s]:=a[i]; inc(i); end
else begin c[s]:=b[j]; inc(j); end;
inc(s);
end;
{один из массивов - частей обработан полностью}
{осталость перенести в с остаток другого массива - части}
while i<=k do
begin c[s]:=a[i]; inc(i); inc(s); end;
while j<=m do
begin c[s]:=b[j]; inc(j); inc(s); end;
end;
procedure sorting2(var p:ar;len:integer);
var f,i,t:integer;
{f - номер просмотра (изменяется от 1 до n-1)
i - номер рассматриваемой пары
t - промежуточная переменная для перестановки местами элементов}
begin
for f:=1 to len-1 do
{цикл по номеру просмотра}
for i:=1 to len-f do
if p[i]>p[i+1] then
{перестановка элементов}
begin
t:=p[i];
p[i]:=p[i+1];
p[i+1]:=t;
end;
end;
begin
k:=n div 2;
m:=n-k;
writeln('Введите исходный массив:');
for i:=1 to n do read(c[i]);
for i:=1 to k do a[i]:=c[i];
for i:=1 to m do b[i]:=c[k+i];
sorting2(a,k);
sorting2(b,m);
sorting4;
writeln('Отсортированный массив:');
for i:=1 to n do write(c[i],' ');
writeln;
end.