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

Сортировка слиянием — это довольно быстрая сортировка, время работы которой О(n * log n). Однако ее недостатком является тот факт, что она требует относительно много памяти.

Итак, пусть дан некоторый неупорядоченный массив int a[maxn].

Основная идея состоит в том, что на каждом шагу мы разбиваем массив на 2 равные части, сортируем их, а потом сливаем два отсортированных куска. То есть получается рекурсивная сортировка, т.к. каждую из этих 2 частей мы будем сортировать аналогично. Выход из рекурсии будет происходить тогда, когда у нас остается меньше 3 элементов. Если их остается всего 2, то меняем их между собой по мере надобности. Если остается только 1 элемент, то оставляем его в покое.

Пример. Пусть дан исходный массив из 7 элементов:

1. 7 4 2 1 0 5 3
2. Шаг 0: 7 4 2 1 0 5 3
3. Шаг 1: 4 7 2 1 0 5 3
4. Шаг 2: 4 7 1 2 0 5 3
5. Шаг 3: 1 2 4 7 0 5 3
6. Шаг 4: 1 2 4 7 0 3 5
7. Шаг 5: 0 1 2 3 4 5 7

Рассмотрим каждый шаг подробно.

Шаг 1:
Сначала рекурсия спустится максимально глубоко, то есть до элементов a[0] и a[1]. Так как 7 > 4, то они поменяются местами.

Шаг 2:

Дальше смотрим на элементы a[3] и a[4]. Так как они тоже стоят неправильно, то меняем их местами.

Шаг 3:

Сейчас крайними являются элементы с индексами 0 и 3. У нас есть 2 отсортированные части. Осталось их слить, чтобы кусок от a[0] до a[3] стал отсортированным. Для этого заведем дополнительный массив buf, куда будем записывать минимальный элемент из левой и правой части. Так как они уже отсортированы, то будем сравнивать самые левые элементы. Так как
1 < 4, то в buf отправится 1. Дальше, по тем же соображениям в buf отправляется 2. Так как в правой части элементы закончились, то в buf отправляются элементы 4 и 7. Теперь когда buf сформирован, помещаем его тсодержимое в массив a.

Шаг 4:

Аналогично поступаем с правой частью, т.е. с куском массива и индексами от 4 до 6.

Шаг 5:

Сливаем левую и правую части. Получаем отсортированный массив.

И картинка для еще большей наглядности:

Код:

#include <iostream>
#include <conio.h>

using namespace std;

#define maxn 100

int a[maxn];

int n;

void merge(int l, int r) {
if (r == l)
return;
if (r — l == 1) {
if (a[r] < a[l])
swap(a[r], a[l]);
return;
}
int m = (r + l) / 2;
merge(l, m);
merge(m + 1, r);
int buf[maxn];
int xl = l;
int xr = m + 1;
int cur = 0;
while (r — l + 1 != cur) {
if (xl > m)
buf[cur++] = a[xr++];
else if (xr > r)
buf[cur++] = a[xl++];
else if (a[xl] > a[xr])
buf[cur++] = a[xr++];
else buf[cur++] = a[xl++];

}
for (int i = 0; i < cur; i++)
a[i + l] = buf[i];
}

int main() {
cin >> n;

for (int i = 0; i < n; i++)
cin >> a[i];

merge(0, n — 1);

for (int i = 0; i < n; i++)
cout << a[i] << » «;

getch();
return 0;
}