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

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

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

Несколько детально этот процесс можно расписать так:

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]
}

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

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

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

#include "stdafx.h"
#include <iostream>
using namespace std;
//функция, сливающая массивы
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()
{
setlocale(LC_ALL, "Rus");
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;
system("pause>>void");
}

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

program Sort_Marge;
uses crt;
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
clrscr;
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], ' ');
readkey;
end.

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