В этой главе рассматривается сортировка слиянием {mergesort), которая является дополнением быстрой сортировки в том, что она состоит из двух рекурсивных вызовов с последующей процедурой слияния.

Одним из наиболее привлекательных свойств сортировки слиянием является тот факт, что она сортирует файл, состоящий из Л элементов, за время, пропорциональное N]ogN, независимо от характера входных данных. В главе 9 мы познакомимся с еще одним алгоритмом, время выполнения которого гарантировано пропорционально NlogN; алгоритм носит название пирамидальной сортировки (heapsort). Основной недостаток сортировки слиянием заключается в том, что прямолинейные реализации этого алгоритма требуют дополнительного пространства памяти, пропорционального N. Это препятствие можно обойти, однако сделать это довольно сложно, причем потребуются дополнительные затраты, которые в общем случае не оправдываются на практике, особенно если учесть, что существует альтернатива в виде пирамидальной сортировки. Получить профаммную реализацию сортировки слиянием не труднее, чем реализацию пирамидальной сортировки, при этом длина внутреннего цикла принимает среднее значение между аналогичными показателями быстрой сортировки и пирамидальной сортировки, следовательно, сортировка методом слияния достойна того, чтобы к ней проявить внимание в случае, когда на первый план выходят такие показатели как быстродействие, необходимость избегать наихудших случаев, возможность использования дополнительного пространства памяти.

Но гарантированное время выполнения, пропорциональное N]ogN, может обернуться недостатком. Например, в главе 6 мы видели, что существуют методы, которые могут быть адаптированы таким образом, что в некоторых особых ситуациях, например, когда уровень упорядоченности файла достаточно высок либо когда имеется всего лишь несколько различных ключей, время их выполнения линейно. В противоположность этому, время выполнения сортировки слиянием зависит главным образом от числа ключей входного файла и оно практически не чувствительно к их порядку.

Сортировка слиянием - это устойчивая сортировка, и данное обстоятельство склоняет чашу весов в ее пользу в тех приложениях, в которых устойчивость имеет важное значение. Конкурирующие методы, такие как быстрая сортировка или пирамидальная сортировка, не относятся к числу устойчивых. Различные приемы, придающие этим методам устойчивость, имеют стойкую тенденцию к использованию дополнительного пространства памяти; следовательно, требования дополнительной памяти, предъявляемые со стороны сортировки слиянием отодвигаются на задний план в тех случаях, когда устойчивость становится доминирующим фактором.

Другое свойство сортировки слиянием, которое приобретает важное значение в некоторых ситуациях, является тот факт, что сортировка слиянием обычно реализуется таким образом, что она осуществляет, в основном, последовательный доступ к данным (один элемент за другим). Например, сортировка слиянием - именно тот метод, который можно применить к связным спискам, для которых из всех методов доступа применим только метод последовательного доступа. По тем же причинам, как мы убедимся в главе И, слияние часто используется в качестве основы для сортировки на специализированных и высокопроизводительных машинах, поскольку именно последовательный доступ к данным в подобного рода системах обработки данных является самым быстрым.

8.1. Двухпутевое слияние

Имея два упорядоченных входных файла, их можно объединить в один упорядоченный выходной файл просто отслеживая наименьший элемент в каждом файле и входя в цикл, в котором меньший из двух элементов, наименьших в своих файлах, переносится в выходной файл; процесс продолжается до тех пор, пока оба входных файла не будут исчерпаны. Мы ознакомимся с несколькими реализации этой базовой абстрактной операции в этом и следующем разделах. Время выполнения линейно зависит от количества элементов в выходном файле, если на каждую операцию поиска следующего наименьшего элемента в файле уходит одно и то же время, что как раз и имеет место в том случае, когда отсортированные файлы представлены структурой данных, которая поддерживает последовательный доступ с постоянным временем доступа, такой как связный список или массив. Эта процедура представляет собой двухпутевое слияние {two-way merging); в главе 11 мы подробно ознакомимся с многопутевым слиянием, в котором принимают участие более двух файлов. Наиболее важным приложением многопутевого слияния является внешняя сортировка, которая подробно рассматривается в текущей главе.

Для начала предположим, что имеются два непересекающихся упорядоченных массива целых чисел a[0],...,a[N-l] и b[0],...,b[M-l], которые требуется слить в третий массив c[0],...,c[N+M-l]. Легко реализуемая очевидная стратегия заключается в том, чтобы последовательно выбирать для с наименьший оставшийся элемент из а и Ь, как показано в профамме 8.1. Эта реализация отличается простотой, в то же время она обладает характеристиками, которые мы сейчас и рассмотрим.

Программа 8.1. Слияние

Чтобы объединить два упорядоченных массива а и b в упорядоченный массив с, используется цикл for, который помещает элемент в массив с на каждой итерации. Если а исчерпан, элемент берется из Ь; если исчерпан Ь, то элемент берется из а; если же элементы остаются и в том и в другом массиве, наименьший из оставшихся элементов в а и b переходит в с. Помимо неявного предположения об упорядоченности обоих массивов, эта реализация предполагает также, что массив с не пересекается (т.е., не перекрывается или совместно не использует памяти) а и Ь.

template <class Item>

void mergeAB(Item c[]. Item a[] , int N,

Item b[] , int M )

for (int i = 0, j = 0, k = 0;k< N+M; k++) {

if (i == N) { c[k] = b[j++]; continue; } if (j == M) { c[k] = a[i++]; continue; } c[k] = (a[i] < b[j]) ? a[i++] : b[j++];

Во-первых, эта реализация предполагает, что массивы не пересекаются. В частности, если а и b являются крупными массивами, то для размещения выходных данных необходим третий массив с (также крупный). Вместо того чтобы использовать дополнительное пространство памяти, пропорциональное размерам слитого файла, жела-

тельно иметь в своем распоряжении такой метод, чтобы с помощью операций обмена мы могли, например, объединить два упорядоченных файла a[l],.*M[in] и а[т+1],...,а[г] в один упорядоченный файл за счет соответствующего перемещения элементов а[1],...,а[г] без использования больших объемов дополнительного пространства памяти. Здесь желательно на какое-то время остановиться и подумать о том, как можно все это сделать. На первый взгляд кажется, что у этой проблемы есть простое решение, однако на самом деле все известные до сих пор решения достаточно сложные, особенно если их сравнить с программой 8.1. И в самом деле, довольно трудно разработать алгоритм обменного слияния, т.е. в рамках пространства памяти, занимаемого входными файлами, который обладал бы лучшими характеристиками и который мог бы стать альтернативой обменной сортировке. Мы вернемся к этой проблеме в разделе 8.2.

Слияние, как операция, имеет свою собственную область применения. Например, в обычной среде обработки данных может возникнуть необходимость поддерживать крупный (упорядоченный) файл данных, в который непрерывно поступают новые элементы. Один из подходов заключается в том, что новые элементы фуппируются в пакеты, которые затем добавляются в главный (намного больший) файл, после чего выполняется очередная сортировка всего файла. Такая ситуация как бы специально создана для слияния: более эффективная стратегия предусматривает сортировку пакета (небольших размеров) новых элементов, с последующим слиянием полученного файла небольших размеров с большим главным файлом. Слияние используется во многих подобного рода приложениях, что обусловливает целесообразность ее изучения. Основное внимание в данное главе будет уделяться методам сортировки, в основу которых положено слияние.

Упражнения

8.1. Предположим, что упорядоченный файл размером нужно объединить с неупорядоченным файлом размером Л/, при этом М намного меньше Л . Во сколько раз быстрее, чем повторная сортировка, работает предложенный метод, в основе которого лежит слияние, если его рассматривать как функцию от М, при

= 10, 10 и 10? Решите эту задачу полагая, что в вашем распоряжении имеется программа сортировки, которой требуется c]N\gN секунд, чтобы выполнить сортировку файла размером N, и программа слияния, которой требуется c2{N + М) секунд, чтобы слить файл размером с файлом размером М, при с\ ~ cj.

8.2. В чем превосходит и в чем уступает сортировка всего файла методом вставок двум методами, представленными в упражнении 8.1? (Ответьте на этот вопрос, полагая, что малый файл имеет произвольную организацию, так что каждая вставка проходит примерно полпути в большом файле, а время выполнения сортировки определяется выражением Сз MN/2, при этом константа Сз - того же порядка, что и другие константы.)

8.3. Что произойдет, если воспользоваться прОфаммой 8.1 для обменного слияния посредством вызова merge(a, а, N/2, a+N/2, N-N/2) применительно к ключам AEQSUYEINOST?