Нисходящая сортировка слиянием
Эта сортировка является рекурсивной операцией, которая делит файл пополам и выполняет по рекурсии сортировку обеих половин. Дерево рекурсии выглядит следующим образом:
Рекурсия ограничена снизу размером разделяемого файла, равным 1. Каждый рекурсивный вызов делит файл пополам. В случае если размер файла кратен 2, получается полное, сбалансированное дерево рекурсии. 
Если n не кратно 2, то дерево получается несбалансированным, но все равно его высота оценивается log2 n. Общий алгоритм нисходящей сортировки слиянием выглядит следующим образом:
НИСХОДЯЩАЯ СОРТИРОВКА СЛИЯНИЕМ
Имея в своем распоряжении процедуру слияния, нетрудно положить ее в осно-
ву рекурсивной процедуры сортировки. Чтобы отсортировать заданный файл, нуж-
но разделить его на две части, рекурсивно отсортировать обе половины и затем слить
их. Реализация этого алгоритма представлена в программе 8.3; а пример показан на
рис. 8.2. Как было сказано в главе 5, этот алгоритм является одним из самых известных
примеров использования принципа “разделяй и властвуй” для разработки эффективных
алгоритмов.
Нисходящая сортировка слиянием аналогична принципу управления сверху вниз,
при котором руководитель разбивает большую задачу на подзадачи, которые должны
независимо решать его подчиненные. Если каждый руководитель будет просто разби-
вать свою задачу на две равные части, а потом объединять решения, полученные его
подчиненными, и передавать результат своему начальству, то получится процесс, ана-
логичный сортировке слиянием. Работа практически не продвигается, пока не получит
свою задачу кто-то, не имеющий подчиненных (в рассматриваемом случае это слияние
двух файлов размером 1); но потом руководство выполняет значительную работу, объе-
диняя результаты работы подчиненных.
Сортировка слиянием играет важную роль благодаря простоте и оптимальности
заложенного в нее метода (время ее выполнения пропорционально N log N), который допускает возможность устойчивой реализации. Эти утверждения сравнительно нетрудно доказать.
Эта базовая реализация сортировки слиянием является примером рекурсивной програм-
мы, основанной на принципе “разделяй и властвуй”. Для упорядочения массива a[1],
..., a[r] он разбивается на две части a[1],..., a[m] и a[m+1],..., a[r], которые сорти-
руются независимо друг от друга (через рекурсивные вызовы) и вновь сливаются для по-
лучения отсортированного исходного файла. Функции merge может потребоваться вспо-
могательный файл, достаточно большой для помещения копии входного файла, однако
эту абстрактную операцию удобно рассматривать как обменное слияние (см. текст).
template <class Item>
void mergesort(Item a[], int l, int r)
{ if (r <= l) return;
int m = (r+l)/2;
mergesort(a, l, m);
mergesort(a, m+1, r);
merge(a, l, m, r);
}
A S O R T I N G E X A M P L E
A S
O R
A O R S
I T
G N
G I N T
A G I N O R S T
E X
A M
A E M X
L P
E L P
A E E L M P X
A A E E G I L M N O P R S T X
Рис. 8.2. Пример нисходя-
Щей сортировки слиянием
В каждой строке показан результат вызова функции merge при выполнении нисходящей сортировки слиянием. Вначале сливаются A и S, и получается A S; потом сливаются O и R, и получается O R .Затем сливаются O R и A S, и получается A O R S. После этого сливаются I T и G N, и получается G I N T, потом
этот результат сливается с A O R S, и получается A G I N O R S T, и т.д. Метод рекурсивно объединяет меньшие упорядоченные файлы в бóльшие.
Восходящая сортировка слиянием
Рассмотрим последовательность слияний, выполняемую рекурсивным алгоритмом:
1 – с –1 1 – с – 1 2 – с – 2 1 – c – 1 1 – c – 1 2 – c – 2 4 – c - 4
Порядок выполнения слияний определяется деревом рекурсии. Однако подфайлы обрабатываются независимо и слияние можно выполнять в различных последовательностях.
Например, так:
1 – с – 1 1 – с – 1 1 – с – 1 1 – с – 1 2 – с – 2 2 – с – 2 4 – с – 4
Эта схема справедлива и для n, не кратных 2.
Например, для n = 7:
1 – с – 1 1 – с – 1 1 – с – 1 2 – с – 2 2 – с – 1 4 – с – 3
Такая схема слияний соответствует восходящему порядку прохода по дереву. Сначала выполняются все слияния 1 – с – 1, что соответствует нижнему уровню дерева, затем все слияния 2 – с – 2, затем слияния 4 – с – 4 и т. д. То есть дерево обходится снизу, с полной обработкой каждого уровня.
06 12 18 42 44 55 67 94
4 – с – 4
12 42 44 55 06 18 67 94
2 – с – 2 2 – с – 2
44 55 12 42 18 94 06 67
1 - c - 1 1 - c - 1 1 - c - 1 1 - c - 1
44 55 12 42 94 18 06 67
Как было сказано в главе 5, у каждой рекурсивной программы имеется нерекурсив-
ный аналог, который хотя и выполняет эквивалентные действия, но может делать это в
другом порядке. Нерекурсивные реализации сортировки слиянием заслуживают деталь-
ного изучения в качестве образцов философии алгоритмов “разделяй и властвуй”.
Рассмотрим последовательность слияний, выполняемую рекурсивным алгоритмом.
Из примера, приведенного на рис. 8.2, видно, что файл размером 15 сортируется сле-
дующей последовательностью слияний:
1-и-1 1-и-1 2-и-2 1-и-1 1-и-1 2-и-2 4-и-4
1-и-1 1-и-1 2-и-2 1-и-1 2-и-1 4-и-3 8-и-7.
Порядок выполнения слияний определяется рекурсивной структурой алгоритма. Но
подфайлы обрабатываются независимо, поэтому слияния могут выполняться в различ-
ном порядке. На рис. 8.4 показана восходящая стратегия, при которой последователь-
ность слияний такова:
1-и-1 1-и-1 1-и-1 1-и-1 1-и-1 1-и-1 1-и-1
2-и-2 2-и-2 2-и-2 2-и-1 4-и-4 4-и-3 8-и-7.
В обоих случаях выполняются семь слияний 1-и-1,
три слияния 2-и-2 и по одному слиянию 2-и-1, 4-и-4,
4-и-3 и 8-и-7, но они выполняются в различном по-
рядке. Восходящая стратегия предлагает сливать наи-
меньшие из оставшихся файлов, проходя по массиву
слева направо.
A S O R T I N G E X A M P L E
A S
O R
I T
G N
E X
A M
L P
A O R S
G I N T
A E M X
E L P
A G I N O R S T
A E E L M P X
A A E E G I L M N O P R S T X
АБСТРАКТНОЕ ОБМЕННОЕ СЛИЯНИЕ
Слияние без
Сигнальных ключей
Для слияния двух упорядоченных по возрастанию файлов они копируются в другой файл, причем второй файл копируется сразу за первым в обратном порядке. Тогда можно следовать следующему простому правилу: в выходной файл выбирается левый или правый элемент — тот, у которого ключ меньше. Максимальный ключ выполняет роль сигнального для обоих файлов, где бы он ни находился. На данном рисунке показано слияние файлов A R S T и G I N.
A R S T G I N
A R S T N I G
R S T N I G A
R S T N I A G
R S T N A G I
R S T A G I N
S T A G I N R
T A G I N R S
A G I N R S T