Восходящая сортировка слиянием

Восходящая сортировка слиянием состоит из последовательности проходов по всему файлу с выполнением слияний вида m -c- m, при этом m на каждом проходе удваивается, так что в заключение производится слияния типа m -c- x для некоторого x, меньшего или равного m.

Нерекурсивный вариант сортировки слиянием в приведенном шаблоне функции получается следующим образом: все элементы файла рассматриваются как упорядоченные подсписки длиной 1. Затем мы рассматриваем этот список, выполняя слияния вида 1-с-1, что дает

упорядоченные подсписки размером 2, затем мы просматриваем полученный список, выполняя при этом слияния вида 2-с-2, что даст упорядоченный подсписок размером 8, и так до тех пор, пока весь список не станет упорядоченным. Завершающий подсписок не всегда может оказаться того же размера, что и все другие, если размер файла не является степенью 2, тем не менее, можно слить и его.

int min(int A,int B)

{return (A<B)?A:B;

}

//Листинг 3 Восходящая сортировка слиянием

template<typename T>

void MergeSortUp(T* a,int left,int right)

{

for(int m=1;m<=right-1;m=m+m)

for(int i=left;i<=right-m;i+=m+m)

{

MergeSort(a,i,i+m-1,min(i+m+m-1,right));

}

}

Дата добавления: 2015-08-17