Специальные методы сортировки a

Реализации сортировки-слияния

Общая стратегия сортировки-слияния, описанная в разделе 11.13, доказала свою эффективность на практике. В данном разделе мы рассмотрим два усовершенствования этой стратегии, позволяющих снизить затраты. Первое из них, метод выборки с замещением (replacement selection), оказывает на время выполнения тот же эффект, что и увеличение объема используемой оперативной памяти; следующий метод, полифазное слияние (polyphase merging), дает тот же эффект, что и увеличение числа используемых устройств.
В разделе 11.3 обсуждалось применение очереди с приоритетами для P-путевого слияния, но при этом было сказано, что P настолько мало, что повышение быстродействия очереди практически ничего не дает. Однако на этапе начального распределения можно воспользоваться быстрыми очередями с приоритетами, чтобы получить отсортированные отрезки, размеры которых больше объема оперативной памяти. Идея заключается в том, чтобы пропустить (неупорядоченные) входные данные через большую очередь с приоритетами - как и раньше, выбирая из очереди с приоритетами наименьший элемент и заменяя его следующим элементом из входных данных, с одним дополнительным условием: если новый элемент меньше, чем только что выбранный из очереди, то, поскольку он может и не стать частью текущего сортируемого блока, мы помечаем его как принадлежащий следующему блоку и считаем, что он больше всех остальных элементов текущего блока. Когда помеченный элемент доходит до вершины очереди с приоритетами, мы начинаем новый блок. Работа этого метода показана на рис. 11.14.


Рис. 11.14. Выбор с замещением
Эта последовательность показывает, как из последовательности A S O R T I N G E X A M P L E можно получить два отрезка данных - A I N O R S T X и A E E G L M P - длиной соответственно 8 и 7, используя для этой цели сортирующее дерево размером 5.
Лемма 11.5. В случае произвольных ключей размеры отрезков данных, полученных выборкой с замещением, примерно в два раза больше размера сортирующего дерева.
Если для получения начальных отрезков воспользоваться пирамидальной сортировкой, то сначала память заполняется записями, затем они выбираются из очереди одна за одной, до опустошения сортирующего дерева. После этого память заполняется очередным пакетом записей, и этот процесс повторяется снова и снова. В среднем во время выполнения этого процесса сортирующее дерево использует только половину отведенной памяти. В противоположность этому, выборка с замещением поддерживает постоянное заполнение оперативной памяти, поэтому неудивительно, что ее эффективность в два раза выше. Полное доказательство этого свойства требует сложного анализа (см. раздел ссылок), хотя его нетрудно проверить экспериментально (см. упражнение 11.47). 
Для случайно упорядоченных файлов практический результат применения выборки с замещением состоит в возможном уменьшении числа проходов на один: вместо того, чтобы начать с отсортированных отрезков с размером, примерно равным объему оперативной памяти, мы можем начать с отрезков в два раза большего размера. Для P = 2 такая стратегия экономит точно один проход слияния, для больших значений P эффект менее заметен. Однако мы знаем, что на практике сортировка случайно упорядоченных файлов встречается редко, и при наличии некоторой упорядоченности использование выборки с замещением может дать отрезки очень больших размеров. Например, если ни одному из ключей в файле не предшествуют более M больших его ключей, то этот файл может быть полностью отсортирован во время прохода выборки с замещением, и слияние вообще не понадобится! Эта возможность служит наиболее веским аргументом в пользу практического применения выборки с замещением.
Главным недостатком сбалансированной многопутевой сортировки является то, что во время слияний активно используется лишь примерно половина внешних устройств: P входных устройств и устройство, на которое записываются выходные данные. Альтернативой этому является выполнение (2P - 1)-путевых слияний с записью на устройство 0 и с распределением данных на другие устройства после каждого прохода слияния. Но этот способ не повышает эффективность, поскольку он удваивает количество проходов распределения данных. Сбалансированное многопутевое слияние, похоже, требует либо дополнительного числа внешних устройств, либо выполнения дополнительных копирований. Разработано несколько хитроумных алгоритмов, которые обеспечивают занятость всех внешних устройств с помощью замены способа, которым сливаются небольшие отсортированные блоки. Простейший из этих методов называется полифазное слияние.
Идея, лежащая в основе полифазного слияния, заключается в неравномерном распределении упорядоченных блоков, которые получаются в результате выборки с замещением, на доступные ленты (оставляя одну ленту пустой) с последующим применением стратегии " сливать до исчерпания " (merge-until-empty): поскольку сливаемые отрезки неодинаковы по длине, одна лента закончится раньше остальных, после чего она может быть использована как выходная. То есть мы меняем ролями выходную ленту (на которой размещено некоторое количество отсортированных блоков) и исчерпанную входную ленту, и продолжаем этот процесс, пока не останется только один блок. Соответствующий пример показан на рис. 11.15.
Стратегия " сливать до исчерпания " работает для произвольного количества лент, как показано на рис. 11.16.