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

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

3 5 6

2 4 7

Будем каждый раз переносить в область вывода меньший из двух наименьших элементов (рис. 34).

Рис 34. Процесс слияния двух последовательностей

Для того, чтобы избавиться от обработки ситуации когда одна из последовательность закончилась, добавим в конец каждой из них искусственных "стражей" - ключи, равные ∞. Ниже представлен текст функции, выполняющей слияние двух сортированных целых массивов в один сортированный массив.

void Merge(int n, int *t, int m, int *v, int *r){

// функция выполняет слияние массива t длиной n и

// массива v длиной m. Результат помещается в массив r

int i=0,j=0,k=0; // индексы для t,v,r

while(i<n && j<m){

if(t[i]<v[j]){

r[k++]=t[i++];

} else {

r[k++]=v[j++];

}

}

}

Простейшая форма сортировки слиянием начинает с подмножеств, состоящих из единичных элементов, и объединяет их попарно в ~ N/2 сортированных

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

подмножеств, содержащих по два элемента. Затем эти подмножества попарно сливаются, и число их уменьшается вдвое и т.д., пока таблица не будет отсортирована полностью. Рис. 35 поясняет этот процесс. Данные поочередно переписываются из одной области памяти в другую. Все слияния, выполняемые при переходе из одной области в другую, требуют не более N сравнений и необходимо ~log₂N таких переходов, следовательно, время сортировки пропорционально N log₂N.

Дата добавления: 2014-12-08