1.3.Метод Слияния.

Сортировка слиянием— алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Пример сортировки слиянием. Сначала делим список на кусочки (по 1 элементу), затем сравниваем каждый элемент с соседним, сортируем и объединяем. В итоге, все элементы отсортированы и объединены вместе.

Для решения задачи сортировки эти три этапа выглядят так:

1.Сортируемый массив разбивается на две части примерно одинакового размера;

2.Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;

3.Два упорядоченных массива половинного размера соединяются в один.

Пример работы алгоритма на массиве 3, 7, 8, 2, 4, 6, 15:

Слияние имеет большое практическое применение. Например ,у Вас есть 2 списка номеров телефонов , отсортированных по возрастанию и их нужно объединить в один список, тоже отсортированный по возрастанию. Перейдем непосредственно к самому алгоритму. Представим , что мы имеем 2 массива M,N , содержащие упорядоченные элементы. Нужно выполнить слияние этих массивов с массивов P. Для этого : вначале сравнивается элемент M[1] с элементом N[1] и меньший из низ записывается в P[1] . Если M[1] меньше N[1] , то при выполнении следующего шага сравниваться уже будут M[2] и N[1], если наоборот - сравнивать будем M[1] и N[2]. И так до тех пор, пока один из начальных массивов не опустошится. Тогда оставшиеся элементы в другом массиве дописываются в массив P.

Попробуем алгоритм в действии. Пусть массив M содержит 3,5,8,11,16 , а массив N содержит 1,5,7,9,12,13,18,20 . Смотрим на схему:

Пример сортировки на языке С++ :

int coun=0; int make_merge(int a[500], int l, int mid,int r){

int nmax=500;

int tmp[nmax];

int i=l;

int j;

j=mid+1;

for(int step=0;step<r-l+1;step++){

if((j>r)||((i<=mid) && (a[i]<a[j])))

{ coun+=j-(mid+1);

tmp[step]=a[i];

i++;

}

else{

tmp[step]=a[j];

j++;

}

}

for(int step=0;step<r-l+1;++step){

a[l+step]=tmp[step];

}}

int merge_sort(int a[500],int l,int r) {

if(l==r) return 0;

int mid =(l+r)/2;

merge_sort(a,l,mid);

merge_sort(a,mid+1,r);

make_merge(a,l,mid,r);

}

int main()