Сортировка Слиянием (Merge-Sort)
- Подробности
- Категория: Сортировка и поиск
Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
- массив рекурсивно разбивается пополам, и каждая из половин делиться до тех пор, пока размер очередного подмассива не станет равным единице;
- далее выполняется операция алгоритма, называемая слиянием. Два единичных массива сливаются в общий результирующий массив, при этом из каждого выбирается меньший элемент (сортировка по возрастанию) и записывается в свободную левую ячейку результирующего массива. После чего из двух результирующих массивов собирается третий общий отсортированный массив, и так далее. В случае если один из массивов закончиться, элементы другого дописываются в собираемый массив;
- в конце операции слияния, элементы перезаписываются из результирующего массива в исходный.
| Худшее время |
O(n log n) |
|---|---|
| Лучшее время |
O(n log n) обычно, O(n) на упорядоченном массиве |
| Среднее время |
O(n log n) |
| Затраты памяти |
O(n) вспомогательных |
Реализация алгоритма на различных языках программирования:
C++
/**
* @brief Сортировка элементов от l до r массива buf
* @param[in/out] buf - сортируемый массив
* @param[in] l - левая граница. При первой итерации l = 0
* @param[in] r - правая граница. При первой итерации r = buf.size() - 1
*
* В результате сортируются все элементы массива buf от l до r включительно.
*/
template<typename Type>
void MergeSort(vector<Type>& buf, size_t l, size_t r)
{
//! Условие выхода из рекурсии
if(l >= r) return;
size_t m = (l + r) / 2;
//! Рекурсивная сортировка полученных массивов
MergeSort(buf, l, m);
MergeSort(buf, m+1, r);
merge(buf, l, r, m);
}
/**
* @brief Слияние элементов.
* @param[in/out] buf - массив
* @param[in] l - левая граница. При певой итерации l = 0
* @param[in] r - правая граница. При первой итерации r = buf.size() - 1
* @param[in] m - граница подмассивов.
*
* Массив buf содержит два отсортированных подмассива:
* - [l; m] - первый отсортированный подмассив.
* - [m+1; r] - второй отсортированный подмассив.
* В результате получаем отсортированный массив, полученный из двух подмассивов,
* который сохраняется в buf[l; r].
*/
template<typename Type>
static void merge(vector<Type>& buf, size_t l, size_t r, size_t m)
{
if (l >= r || m < l || m > r) return;
if (r == l + 1 && buf[l] > buf[r]) {
swap(buf[l], buf[r]);
return;
}
vector<Type> tmp(&buf[l], &buf[l] + (r + 1));
for (size_t i = l, j = 0, k = m - l + 1; i <= r; ++i) {
if (j > m - l) {
buf[i] = tmp[k++];
} else if(k > r - l) {
buf[i] = tmp[j++];
} else {
buf[i] = (tmp[j] < tmp[k]) ? tmp[j++] : tmp[k++];
}
}
}
Существует также итеративный алгоритм сортировки, избавленный от рекурсивных вызовов. Такой алгоритм называют «Восходящей сортировкой слиянием».
// Слияние двух упорядоченных массивов
// m1 - Первый массив
// m2 - Второй массив
// l1 - Длина первого массива
// l2 - Длина второго массива
// Возвращает объединённый массив
template <class T>
T* merge(T *m1, T* m2, int l1, int l2)
{
T* ret = new T[l1+l2];
int n = 0;
// Сливаем массивы, пока один не закончится
while (l1 && l2) {
if (*m1 < *m2) {
ret[n] = *m1;
m1++;
--l1;
} else {
ret[n] = *m2;
++m2;
--l2;
}
++n;
}
// Если закончился первый массив
if (l1 == 0) {
for (int i = 0; i < l2; ++i) {
ret[n++] = *m2++;
}
} else { // Если закончился второй массив
for (int i = 0; i < l1; ++i) {
ret[n++] = *m1++;
}
}
return ret;
}
// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len)
{
int n = 1, l, ost;
T * mas1;
while (n < len) {
l = 0;
while (l < len) {
if (l + n >= len) break;
ost = (l + n * 2 > len) ? (len - (l + n)) : n;
mas1 = merge(mas + l, mas + l + n, n, ost);
for (int i = 0; i < n + ost; ++i)
mas[l+i] = mas1[i];//тут нужно что-то поменять, потому что это лишнее копирование, и оно увеличивает время работы алгоритма в два раза
delete [] mas1;
l += n * 2;
}
n *= 2;
}
}
Пример: char a[] = "ASORTINGEXAMPLE"; mergeSort(a, 16); Альтернативная версия алгоритма Сортировки Слиянием.
template <typename Item>
void Merge(Item Mas[], int left, int right, int medium)
{
int j = left;
int k = medium + 1;
int count = right - left + 1;
if (count <= 1) return;
Item *TmpMas = new Item[count];
for (int i = 0; i < count; ++i) {
if (j <= medium && k <= right) {
if (Mas[j] < Mas[k])
TmpMas[i] = Mas[j++];
else
TmpMas[i] = Mas[k++];
} else {
if (j <= medium)
TmpMas[i] = Mas[j++];
else
TmpMas[i] = Mas[k++];
}
}
j = 0;
for (int i = left; i <= right; ++i) {
Mas[i] = TmpMas[j++];
}
delete[] TmpMas;
}
template <typename Item>
void MergeSort(Item a[], int l, int r)
{
int m;
// Условие выхода из рекурсии
if(l >= r) return;
m = (l + r) / 2;
// Рекурсивная сортировка полученных массивов
MergeSort(a, l, m);
MergeSort(a, m + 1, r);
Merge(a, l, r, m);
}
C#
static Int32[] Merge_Sort(Int32[] massive)
{
if (massive.Length == 1)
return massive;
Int32 mid_point = massive.Length / 2;
return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray()));
}
static Int32[] Merge(Int32[] mass1, Int32[] mass2)
{
Int32 a = 0, b = 0;
Int32[] merged = new int[mass1.Length + mass2.Length];
for (Int32 i = 0; i < mass1.Length + mass2.Length; i++)
{
if (b < mass2.Length && a < mass1.Length)
if (mass1[a] > mass2[b])
merged[i] = mass2[b++];
else //if int go for
merged[i] = mass1[a++];
else
if (b < mass2.Length)
merged[i] = mass2[b++];
else
merged[i] = mass1[a++];
}
return merged;
}
static void Main(string[] args)
{
Int32[] arr = new Int32[100];
//заполняем массив случайными числами
Random rd = new Random();
for(Int32 i = 0; i < arr.Length; ++i) {
arr[i] = rd.Next(1, 101);
}
System.Console.WriteLine("The array before sorting:");
foreach (Int32 x in arr)
{
System.Console.Write(x + " ");
}
//сортировка
arr = Merge_Sort(arr);
System.Console.WriteLine("\n\nThe array after sorting:");
foreach (Int32 x in arr)
{
System.Console.Write(x + " ");
}
System.Console.WriteLine("\n\nPress the <Enter> key");
System.Console.ReadLine();
}
C#
//предыдущий пример сортирует лишь целые числа. Следующий - работает со всеми типами данных.
static IComparable[] Merge_Sort(IComparable[] massive)
{
if (massive.Length == 1)
return massive;
int mid_point = massive.Length / 2;
return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray()));
}
static IComparable[] Merge(IComparable[] mass1, IComparable[] mass2)
{
int a = 0, b = 0;
IComparable[] merged = new IComparable[mass1.Length + mass2.Length];
for (int i = 0; i < mass1.Length + mass2.Length; i++)
{
if (b.CompareTo(mass2.Length) < 0 && a.CompareTo(mass1.Length) < 0)
if (mass1[a].CompareTo(mass2[b]) > 0)
merged[i] = mass2[b++];
else
merged[i] = mass1[a++];
else
if (b < mass2.Length)
merged[i] = mass2[b++];
else
merged[i] += mass1[a++];
}
return merged;
}
static void Main(string[] args)
{
IComparable[] arr = new IComparable[100];
Random rd = new Random();
for (int i = 0; i < arr.Length; ++i)
arr[i] = rd.Next(1, 101);
Console.WriteLine("Массив перед сортировкой:");
foreach (int x in arr)
System.Console.Write(x + " ");
arr = Merge_Sort(arr);
Console.WriteLine("\n\nМассив после сортировки:");
foreach (int x in arr)
System.Console.Write(x + " ");
Console.WriteLine("\n\nДля выхода нажмите <Enter>.");
Console.ReadKey();
}
Perl
@out=(5,2,8,9,4,2,7,9,4,1,6,9,0);
sub sortM{
my($array,$first,$last)=@_;
if($last>$first){
my$middle=int(($last+$first)/2);
sortM($array,$first,$middle);
sortM($array,$middle+1,$last);
my$j=0;
$work[$j++]=$$array[$_]for($first..$last);
$middle=int(($first+$last)/2)if($middle>$last);
my$n=$middle-$first+1;
for($i=$first,$j=0,$k=$n;$i<=$last;$i++){
if(($j<$n)&&(($k==(($last-$first)+1))||($work[$j]lt$work[$k]))){
$$array[$i]=$work[$j++]
}else{
$$array[$i]=$work[$k++];
}
}
}
}
sortM(\@out,0,$#out+1);
Паскаль (сортировка текстовых файлов)
Сортировка простым слиянием
Procedure MergeSort(name: string; var f: text);
Var a1,a2,s,i,j,kol,tmp: integer;
f1,f2: text;
b: boolean;
Begin
kol:=0;
Assign(f,name);
Reset(f);
While not EOF(f) do
begin
read(f,a1);
inc(kol);
End;
Close(f);
Assign(f1,'{имя 1-го вспомогательного файла}');
Assign(f2,'{имя 2-го вспомогательного файла}');
s:=1;
While (s<kol) do
begin
Reset(f); Rewrite(f1); Rewrite(f2);
For i:=1 to kol div 2 do
begin
Read(f,a1);
Write(f1,a1,' ');
End;
If (kol div 2) mod s<>0 then
begin
tmp:=kol div 2;
While tmp mod s<>0 do
begin
Read(f,a1);
Write(f1,a1,' ');
inc(tmp);
End;
End;
While not EOF(f) do
begin
Read(f,a2);
Write(f2,a2,' ');
End;
Close(f); Close(f1); Close(f2);
Rewrite(f); Reset(f1); Reset(f2);
Read(f1,a1);
Read(f2,a2);
While (not EOF(f1)) and (not EOF(f2)) do
begin
i:=0; j:=0;
b:=true;
While (b) and (not EOF(f1)) and (not EOF(f2)) do
begin
If (a1<a2) then
begin
Write(f,a1,' ');
Read(f1,a1);
inc(i);
End
else
begin
Write(f,a2,' ');
Read(f2,a2);
inc(j);
End;
If (i=s) or (j=s) then b:=false;
End;
If not b then
begin
While (i<s) and (not EOF(f1)) do
begin
Write(f,a1,' ');
Read(f1,a1);
inc(i);
End;
While (j<s) and (not EOF(f2)) do
begin
Write(f,a2,' ');
Read(f2,a2);
inc(j);
End;
End;
End;
While not EOF(f1) do
begin
tmp:=a1;
Read(f1,a1);
If not EOF(f1) then
Write(f,tmp,' ')
else
Write(f,tmp);
End;
While not EOF(f2) do
begin
tmp:=a2;
Read(f2,a2);
If not EOF(f2) then
Write(f,tmp,' ')
else
Write(f,tmp);
End;
Close(f); Close(f1); Close(f2);
s:=s*2;
End;
Erase(f1);
Erase(f2);
End;
Сортировка естественным слиянием
Procedure MergeSort(name: string; var f: text);
Var s1,s2,a1,a2,where,tmp: integer;
f1,f2: text;
Begin
s1:=5; s2:=5; {Можно задать любые числа, которые запустят цикл while}
Assign(f,name);
Assign(f1,'{имя 1-го вспомогательного файла}');
Assign(f2,'{имя 2-го вспомогательного файла}');
While (s1>1) and (s2>=1) do
begin
where:=1;
s1:=0; s2:=0;
Reset(f); Rewrite(f1); Rewrite(f2);
Read(f,a1);
Write(f1,a1,' ');
While not EOF(f) do
begin
read(f,a2);
If (a2<a1) then
begin
Case where of
1: begin
where:=2;
inc(s1);
End;
2: begin
where:=1;
inc(s2);
End;
End;
End;
Case where of
1: write(f1,a2,' ');
2: write(f2,a2,' ');
End;
a1:=a2;
End;
If where=2 then
inc(s2)
else
inc(s1);
Close(f); Close(f1); Close(f2);
Rewrite(f); Reset(f1); Reset(f2);
Read(f1,a1);
Read(f2,a2);
While (not EOF(f1)) and (not EOF(f2)) do
begin
If (a1<=a2) then
begin
Write(f,a1,' ');
Read(f1,a1);
End
else
begin
Write(f,a2,' ');
Read(f2,a2);
End;
End;
While not EOF(f1) do
begin
tmp:=a1;
Read(f1,a1);
If not EOF(f1) then
Write(f,tmp,' ')
else
Write(f,tmp);
End;
While not EOF(f2) do
begin
tmp:=a2;
Read(f2,a2);
If not EOF(f2) then
Write(f,tmp,' ')
else
Write(f,tmp);
End;
Close(f); Close(f1); Close(f2);
End;
Erase(f1);
Erase(f2);
End;
Delphi (сортировка произвольных типов данных - простое слияние)
unit uMergeSort;
interface
type
TItem = Integer; //Здесь можно написать Ваш произвольный тип
TArray = array of TItem;
procedure MergeSort(var Arr: TArray);
implementation
function IsBigger(d1, d2 : TItem) : Boolean;
begin
Result := (d1 > d2); //Сравниваем d1 и d2. Не обязательно так. Зависит от Вашего типа.
//Сюда можно добавить счетчик сравнений
end;
//Процедура сортировки слияниями
procedure MergeSort(var Arr: TArray);
var
tmp : TArray; //Временный буфер
//Слияние
procedure merge(L, Spl, R : Integer);
var
i, j, k : Integer;
begin
i := L;
j := Spl + 1;
k := 0;
//Выбираем меньший из первых и добавляем в tmp
while (i <= Spl) and (j <=R) do
begin
if IsBigger(Arr[i], Arr[j]) then
begin
tmp[k] := Arr[j];
Inc(j);
end
else
begin
tmp[k] := Arr[i];
Inc(i);
end;
Inc(k);
end;
//Просто дописываем в tmp оставшиеся эл-ты
if i <= Spl then //Если первая часть не пуста
for j := i to Spl do
begin
tmp[k] := Arr[j];
Inc(k);
end
else //Если вторая часть не пуста
for i := j to R do
begin
tmp[k] := Arr[i];
Inc(k);
end;
//Перемещаем из tmp в arr
Move(tmp[0], Arr[L], k*SizeOf(TItem));
end;
//Сортировка
procedure sort(L, R : Integer);
var
splitter : Integer;
begin
//Массив из 1-го эл-та упорядочен по определению
if L >= R then Exit;
splitter := (L + R) div 2; //Делим массив пополам
sort(L, splitter); //Сортируем каждую
sort(splitter + 1, R); //часть по отдельности
merge(L, splitter, R); //Производим слияние
end;
//Основная часть процедуры сортировки
begin
SetLength(tmp, Length(Arr));
sort(0, Length(Arr) - 1);
SetLength(tmp, 0);
end;
end.
D
void mergeSort(int[] array) {
static void merge(int[] array, int q) {
int[] leftArray = array[0..q].dup ~ int.max;
int[] rightArray = array[q..$].dup ~ int.max;
int i = 0;
int j = 0;
int length = array.length;
for (int k = 0; k < length; ++k) {
array[k] = (leftArray[i] <= rightArray[j]) ? leftArray[i++] : rightArray[j++];
}
}
if (array.length > 1) {
int q = array.length / 2;
mergeSort(array[0..q]);
mergeSort(array[q..$]);
merge(array, q);
}
}
Python 2.7 (функциональная реализация)
def merge(right, left, result):
result.append((left if left[0] < right[0] else right).pop(0))
return merge(right=right, left=left, result=result) if left and right else result+left+right
merge_sort = (lambda arr: arr if len(arr) == 1 else merge(merge_sort(arr[len(arr)/2:]),
merge_sort(arr[:len(arr)/2]), []))
Недостатком сортировки слиянием является использование дополнительной памяти. Но когда работать приходиться с файлами или списками, доступ к которым осуществляется только последовательно, то очень удобно применять именно этот метод. Также, к достоинствам алгоритма стоит отнести его устойчивость и неплохую скорость работы O(n*logn).
При написании статьи были использованы открытые источники сети интернет :
