Сортировка слиянием

Алгоритм сортировки слиянием был предложен праотцом современных компьютеров – Джоном фон Нейманом. Сам метод является устойчивым, т. е. он не меняет одинаковые по значению элементы в списке.

В основе сортировки слиянием лежит принцип «разделяй и властвуй». Список разделяется на равные или практически равные части, каждая из которых сортируется отдельно. После чего уже упорядоченные части сливаются воедино. Несколько детально этот процесс можно расписать так:

1. массив рекурсивно разбивается пополам, и каждая из половин делиться до тех пор, пока размер очередного подмассива не станет равным единице;

2. далее, выполняется операция алгоритма, называемая слиянием. Два единичных массива сливаются в общий результирующий массив, при этом из каждого выбирается меньший элемент (сортировка по возрастанию) и записывается в свободную левую ячейку результирующего массива. После чего из двух результирующих массивов собирается третий общий отсортированный массив, и так далее. В случае если один из массивов закончиться, элементы другого дописываются в собираемый массив;

3. в конце операции слияния, элементы перезаписываются из результирующего массива в исходный.

Подпрограмма MergeSort рекурсивно разбивает и сортирует массив, а Merge отвечает за его слияние. Так можно записать псевдокод основной подпрограммы:

 

Подпрограмма MergeSort(A, first, last)

A – массив

first, last – номера первого и последнего элементов соответственно

Если first<last то

{

Вызов MergeSort(A, first, (first+last)/2) //сортировка левой части

Вызов MergeSort(A, (first+last)/2+1, last) //сортировка правой части

Вызов Merge(A, first, last) //слияние двух частей

}

 

Эта подпрограмма выполняется только в том случае, если номер первого элемента меньше номера последнего. Как уже говорилось, из подпрограммы MergeSort вызывается подпрограмма Merge, которая выполняет операцию слияния. Перейдем к рассмотрению последней.

Работа Merge заключается в образовании упорядоченного результирующего массива путем слияния двух также отсортированных массивов меньших размеров. Вот псевдокод этой подпрограммы:

 

Подпрограмма Merge(A, first, last)

{

start, final – номера первых элементов левой и правой частей

mas – массив, middle - хранит номер среднего элемента

middle=(first+last)/2 //вычисление среднего элемента

start=first //начало левой части

final=middle+1 //начало правой части

Цикл j=first до last выполнять //выполнять от начала до конца

Если ((start<=middle) и ((final>last) или (A[start]<A[final]))) то

{

mas[j]=A[start]

увеличить start на 1

}

Иначе

{

mas[j]=A[final]

увеличить final на 1

}

Цикл j=first до last выполнять //возвращение результата в список

A[j]=mas[j]

}

 

Разберем алгоритм сортировки слиянием на следующем примере (рис. 6.10). Имеется неупорядоченная последовательность чисел: 2, 6, 7, 1, 3, 5, 0, 4. После разбивки данной последовательности на единичные массивы, процесс сортирующего слияния (по возрастанию) будет выглядеть так:

 

Рисунок 6.10 – Пример сортировки слиянием

 

Массив был разделен на единичные массивы, которые алгоритм сливает попарно до тех пор, пока не получится один массив, все элементы которого стоят на своих позициях.

Код программы на C++:

 

void Merge(int *A, int first, int last) //функция, сливающая массивы

{

int middle, start, final, j;

int *mas=new int[100];

middle=(first+last)/2; //вычисление среднего элемента

start=first; //начало левой части

final=middle+1; //начало правой части

for(j=first; j<=last; j++) //выполнять от начала до конца

if ((start<=middle) && ((final>last) || (A[start]<A[final])))

{

mas[j]=A[start];

start++;

}

else

{

mas[j]=A[final];

final++;

}

for (j=first; j<=last; j++) A[j]=mas[j]; //возвращение результата в список

delete[]mas;

};

 

void MergeSort(int *A, int first, int last) //рекурсивная процедура сортировки

{

if (first<last)

{

MergeSort(A, first, (first+last)/2); //сортировка левой части

MergeSort(A, (first+last)/2+1, last); //сортировка правой части

Merge(A, first, last); //слияние двух частей

}

};

 

void main() //главная функция

{

int i, n;

int *A=new int[100];

cout<<"Размер массива > "; cin>>n;

for (i=1; i<=n; i++)

{

cout<<i<<" элемент > ";

cin>>A[i];

}

MergeSort(A, 1, n); //вызов сортирующей процедуры

cout<<"Упорядоченный массив: "; //вывод упорядоченного массива

for (i=1; i<=n; i++) cout<<A[i]<<" ";

delete []A;

}

 

Код программы на Pascal:

 

type massiv=array[1..100] of integer;

var n, i: integer;

A: massiv;

procedure Merge(var A: massiv; first, last: integer); {процедура, сливающая массивы}

var middle, start, final , j: integer;

mas: massiv;

begin

middle:=(first+last) div 2; {вычисление среднего элемента}

start:=first; {начало левой части}

final:=middle+1; {начало правой части}

for j:=first to last do {выполнять от начала до конца}

if (start<=middle) and ((final>last) or (A[start]<A[final])) then

begin

mas[j]:=A[start];

inc(start);

end

else

begin

mas[j]:=A[final];

inc(final);

end;

for j:=first to last do A[j]:=mas[j]; {возвращение результата в массив}

end;

 

procedure MergeSort(var A: massiv; first, last: integer); {рекурсивная процедура сортировки}

begin

if first<last then

begin

MergeSort(A, first, (first+last) div 2); {сортировка левой части}

MergeSort(A, (first+last) div 2+1, last); {сортировка правой части}

Merge(A, first, last); {слияние двух частей}

end;

end;

 

begin {основной блок программы}

write('Размер массива > ');

readln(n);

for i:=1 to n do

begin

write(i, ' элемент > ');

read(A[i]);

end;

MergeSort(A, 1, n); {вызов сортирующей процедуры}

write('Упорядоченный массив: '); {вывод отсортированного массива}

for i:=1 to n do write(A[i], ' ');

end.

Недостатком сортировки слиянием является использование дополнительной памяти. Но когда работать приходиться с файлами или списками, доступ к которым осуществляется только последовательно, то очень удобно применять именно этот метод. Также, к достоинствам алгоритма стоит отнести его устойчивость и неплохую скорость работы O(n*log n).