Сортировка слиянием
Слияние означает объединение двух или более упорядоченных таблиц в одну. Например, можно слить две таблицы с ключами:
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 сравнений и необходимо ~log2N таких переходов, следовательно, время сортировки пропорционально N log2N.