Рассматривается сортировка слиянием (mergesort), которая является дополнением быстрой сортировки в том, что она состоит из двух рекурсивных вызовов с последующей процедурой слияния.
Одним из наиболее привлекательных свойств сортировки слиянием является тот факт, что она сортирует массив, состоящий из N элементов, за время, пропорциональное NlogN, независимо от характера входных данных.
Сортировка слиянием — это устойчивая сортировка, и данное обстоятельство склоняет чашу весов в ее пользу в тех приложениях, в которых устойчивость имеет важное значение.
Другое свойство сортировки слиянием, которое приобретает важное значение в некоторых ситуациях, является тот факт, что сортировка слиянием обычно реализуется таким образом, что она осуществляет, в основном, последовательный доступ к данным (один элемент за другим).
Имея два упорядоченных входных массива, их можно объединить в один упорядоченный выходной массив просто отслеживая наименьший элемент в каждом массиве и входя в цикл, в котором меньший из двух элементов, наименьших в своих массивах, переносится в выходной массив; процесс продолжается до тех пор, пока оба входных массива не будут исчерпаны.
Листинг: Алгоритм сортировки слиянием
//-------------------------------------------------------------
// Шаблон move задает вспомогательную функцию, которая просто
// переносит элементы массива из одного фрагмента массива
// в другой фрагмент того же самого или другого массива.
// - Key - класс, задающий тип элементов массива;
// - src - исходный фрагмент массива;
// - sLow, sHigh - индексы, задающие диапазон в исходном массиве;
// - dst - результирующий фрагмент массива;
// - dLow - индекс, задающий нижнюю границу результирующего массива.
//-------------------------------------------------------------
template <class Кеу>
void move(Key * src, int sLow, int sHigh, Key * dst, int dLow) {
for (int pSrc = sLow, pDst = dLow; pSrc <= sHigh;) { dst[pDst++] = src[pSrc++];
}
}
//-------------------------------------------------------------
// Шаблон mergeSort задает функцию сортировки элементов
// массива методом последовательного слияния.
// - Key - класс, задающий тип элементов массива;
// - array - упорядочиваемый массив;
// - low, high - индексы, задающие диапазон сортировки.
//-------------------------------------------------------------
template <class Кеу>
void mergeSort(Key * array, int low, int high) {
// Предполагается, что в начале работы low <= high
// В результате сортировки получается упорядоченный фрагмент
// массива в диапазоне от low до high
int n = high - low +1; // Длина массива
int frag = n; // Число упорядоченных фрагментов
int len = 1; // Длина сливаемых фрагментов
Key * source = array, // Массив, из которого происходит слияние
* dest = new Key[n]; // Массив, в который происходит слияние
int sourceLow = low, // Нижняя граница индексов массива-источника
destLow = 0; // Нижняя граница индексов массива-назначения
while (frag > 1) {
// Один шаг цикла слияния состоит в попарном слиянии фрагментов
// исходного массива и переносе оставшихся неслитыми элементов
// из исходного массива в результирующий.
// Индексы pSource и pDest задают нижние границы этих массивов,
int pSource = sourceLow, pDest = destLow;
do {
int nextSource =min(pSource + 2*len, sourceLow + n);
// Выполняем слияние двух фрагментов или
// перенос последнего оставшегося фрагмента
if (nextSource > pSource + len) {
merge<Key>(source, pSource, pSource+len-1, source, pSource+len, nextSource-1, dest, pDest);
} else {
move<Key>(source, pSource, nextSource-1, dest, pDest);
}
pSource = nextSource;
pDest += 2*len; }
while (pSource < sourceLow+n);
len*= 2; // Длина фрагментов увеличивается вдвое
frag = (frag+l)/2; // Число фрагментов уменьшается вдвое
// Переставляем местами массивы источника и назначения:
Key * tempArray = dest; dest =source; source = tempArray;
int tempLow = destLow; destLow = sourceLow; sourceLow = tempLow;
}
// Если в конце работы результат оказался не на месте,
//то организуется его перенос в исходный массив
if (source != array) {
move<Key>(source, sourceLow, sourceLow+n-1, dest, destLow);
}
}