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

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

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

1. разбить имеющиеся элементы массива на пары и осуществить слияние элементов каждой пары, получив отсортированные цепочки длины 2 (кроме, быть может, одного элемента, для которого не нашлось пары);

2. разбить имеющиеся отсортированные цепочки на пары, и осуществить слияние цепочек каждой пары;

3. если число отсортированных цепочек больше единицы, перейти к шагу 2.

Проще всего формализовать этот алгоритм рекурсивным способом (в следующем разделе мы реализуем этот алгоритм итерационным способом). Функция сортирует участок массива от элемента с номером a до элемента с номером b:

(3)

Поскольку функция сортирует лишь часть массива, то при слиянии двух фрагментов ей не остаётся ничего, кроме как выделять временный буфер для результата слияния, а затем копировать данные обратно:

template<class T> void MergeSort(T *const A, int const n)
{ //Отсортировать массив A, содержащий n элементов

if( n < 2 ) return; //Сортировка не нужна

if( n == 2 ) //Два элемента проще поменять местами,
{ // если нужно, чем делать слияние
if( A[0] > A[1] ) { T const t(A[0]); A[0]=A[1]; A[1]=t; }
return;
}

MergeSort(A , n/2 ); //Сортируем первую половину
MergeSort(A+n/2, n-n/2); //Сортируем вторую половину

T *const B( new T[n] ); //Сюда запишем результат слияния

Merge(A,n/2, A+n/2,n-n/2, B); //Слияние половин

//Копирование результата слияния в исходный массив:
for(int i(0); i<n; ++i) A[i]=B[i];

delete[n] B; //Удаляем временный буфер
}

Листинг 2. Реализация сортировки слиянием

Время работы сортировки слиянием составляет . Пример работы процедуры показан на рисунке:

Рис. 2. Пример работы рекурсивного алгоритма сортировки слиянием

⇐ Предыдущая 123 Следующая ⇒

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

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