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

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Визуализатор: rain.ifmo.ru  [Java]

Реализация:

1. void merge (vector<int> &mas, int l, int m, int r)
2. {
3.   vector<int> buffer(r - l + 1); // результирующий массив
4.   int pos1 = l;  // начальная позициция первого подмассива
5.   int pos2 = m+1; // начальная позиция второго подмассива
6.   int posB = 0;  // начальная позиция результирующего массива
7.  
8.   while (pos1<=m && pos2<=r)
9.   {
10.     if (mas[pos1]<mas[pos2])
11.       buffer[posB++] = mas[pos1++];
12.     else
13.       buffer[posB++] = mas[pos2++];
14.   }
15.   while (pos1<=m)
16.     buffer[posB++] = mas[pos1++];
17.   while (pos2<=r)
18.     buffer[posB++] = mas[pos2++];
19.  
20.   copy(buffer.begin(),buffer.end(),mas.begin() + l);
21.   buffer.clear();
22. }
23. void merge_sort(vector<int> &mas, int l, int r)
24. {
25.   if (l == r) // спустились до 1 элемента
26.     return;
27.   int m = (l + r)>>1;
28.   merge_sort(mas,l,m);
29.   merge_sort(mas,m+1,r);
30.  
31.   merge(mas,l,m,r);
32. }

* This source code was highlighted with Source Code Highlighter.

Хотя сортировка слиянием и имеет сложность O(N*logN), но константа у нее может быть велика. В первую очередь это связано с созданием временного массива(buffer) в функции merge. Для того, чтобы просто отсортировать массив больше подойдет алгоритм Быстрой сортировки. Но тем не менее важно знать и уметь использовать механизм слияния двух отсортированных массивов.