Алгоритм сортировки слиянием был предложен праотцом современных компьютеров – Джоном фон Нейманом. Сам метод является устойчивым, т. е. он не меняет одинаковые по значению элементы в списке.
В основе сортировки слиянием лежит принцип «разделяй и властвуй». Список разделяется на равные или практически равные части, каждая из которых сортируется отдельно. После чего уже упорядоченные части сливаются воедино.
Несколько детально этот процесс можно расписать так:
- массив рекурсивно разбивается пополам, и каждая из половин делиться до тех пор, пока размер очередного подмассива не станет равным единице;
- далее выполняется операция алгоритма, называемая слиянием. Два единичных массива сливаются в общий результирующий массив, при этом из каждого выбирается меньший элемент (сортировка по возрастанию) и записывается в свободную левую ячейку результирующего массива. После чего из двух результирующих массивов собирается третий общий отсортированный массив, и так далее. В случае если один из массивов закончиться, элементы другого дописываются в собираемый массив;
- в конце операции слияния, элементы перезаписываются из результирующего массива в исходный.
Основная подпрограмма 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).