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

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

Пример. Пусть дан исходный массив из 7 элементов: 7 4 2 1 0 5 3

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

Рисунок7

Существует несколько видов сортировки слиянием, но мы разберем только общий: двухпутевое слияние, абстрактное обменное слияние, нисходящая сортировка слиянием, восходящая сортировка слиянием, производительностьсортировкислиянием.

Реализациякода:

#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);
intbuf[maxn];
int xl = l;
intxr = 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 (inti = 0; i< cur; i++)
a[i + l] = buf[i];
}
int main() {
cin>> n;
for (inti = 0; i< n; i++)
cin>> a[i];
merge(0, n - 1);
for (inti = 0; i< n; i++)
cout<< a[i] << " ";
getch();
return 0;
}

//рекурсивнаясортировка

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); //слияниедвухчастей

}

}

};

//главнаяфункция

int main()

{

inti, 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");

}

Достоинства:

· Работает даже на структурах данных последовательного доступа.

· Хорошо сочетается с подкачкой и кэшированием памяти.

· Неплохо работает в параллельном варианте: легко разбить задачи между процессорами поровну, но трудно сделать так, чтобы другие процессоры взяли на себя работу, в случае если один процессор задержится.

· Не имеет «трудных» входных данных.

· Устойчивая - сохраняет порядок равных элементов (принадлежащих одному классу эквивалентности по сравнению).

Недостатки:

· На «почти отсортированных» массивах работает столь же долго, как на хаотичных.

· Требует дополнительной памяти по размеру исходного массива.