Глава 5. Внешняя сортировка

5.1. Многопутевое слияние

Напомним, что под слиянием уже отсортированных совокупностей данных (файлов) понимается сортировка их объединения.

Быстрая оперативная память компьютера имеет значительно меньший объём по сравнению с ёмкостью медленных периферийных запоминающих устройств ― дисков, магнитных барабанов, магнитных лент. Скорость работы последних определяется скоростью не электронных, а значительно более медленных механических процессов. Поэтому рассмотренные выше методы внутренней сортировки данных, предполагающие большое число сравнений и обменов, оказываются непригодными.

Основной принцип сортировки информации, расположенной на внешних носителях ― сортировка отдельных частей файла в оперативной памяти, их возвращение на внешние носители и последующее слияние.

Слияние оперирует с данными, имеющими структуру линейных списков и обрабатываемыми последовательно по схемам стека и очереди. Подлежащие слиянию отсортированные части файла будем называть сериями, а внешние устройства ― лентами.

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

В процессе слияния используются четыре вспомогательных рабочих ленты.

На первой фазе производится распределение исходного файла на частей длины: части файла длиныпоследовательно записываются в оперативную память, и там сортируются, после чего полученныеначальные серии размещаются поочерёдно на ленте 1 и ленте 2 вплоть до исчерпания всего файла. Значение зависит от объёма доступной оперативной памяти, а значениеот длины файла и от.

На второй фазе ленты перематываются к началу, и производится попарное слияние находящихся на них серий. Полученные серии длины размещаются поочерёдно на ленте 3 и ленте 4. Затем все ленты снова перематываются к началу, и содержимое лент 3 и 4 сливается в серии (снова удвоенной) длинына ленты 1 и 2 (рис. 30).

Рис. 30.

Зацикливание второй фазы последовательно уменьшает количество сливаемых серий и удваивает их длину. Процесс заканчивается, когда останется одна серия, то есть полностью отсортированный файл.

Если исходное количество серий нечетно, то можно формально считать, что на лентенаходится ещё одна серия нулевой длины.При слиянии серий необязательно, чтобы они имели одинаковую длину.

Если доступный при внутренней сортировке объём оперативной памяти вынуждает на этапе распределения разбить исходный файл на серий, где, то алгоритм двухпутевого слияния осуществитпроходов по всем данным (при этом).

Ввиду равномерного распределения серий как между лентами 1 и 2, так и между лентами  3 и 4, слияние называют сбалансированным. При сбалансированном слиянии после фазы распределения количество серий на разных лентах отличается друг от друга не более чем на единицу.

5.1.2. P/q -путевое слияние

Алгоритм двухпутевого слияния, использующий четыре рабочих ленты (назовём его 2/2-путевым) следующим образом обобщается на более общий случай использования рабочих лент при.

рабочих лент разбиваются на два банка ― первый («левый») банк из лент, аналогичных лентам лент 1 и 2, и второй («правый») банк излент (). На фазе распределения исходные серии размещаются поочерёдно на ленты левого банка, и после-путевого слияния в оперативной памяти разносятся поочерёдно полентам правого банка. После этого в обратном направлении сливаютсясерий из левого банка и разносятся полентам левого банка. Процесс продолжается циклически вплоть до получения единственной серии ― всего отсортированного файла.

Значение обычно выбирается равным.

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

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

Актуальность внешней сортировки снижается по мере удешевления быстрых внешних дисковых накопителей и радикального увеличения как их ёмкости, так и размеров оперативной памяти. Далее цитата из классика: «Однако большинство подобных схем сортировки настолько изящны, а соответствующие алгоритмы так отражают глубокие исследования, выполненные в ранние годы компьютеризации, что делать их достоянием только истории науки было бы слишком большим расточительством» ([9], с. 277).

Описанная сортировка называется двухфазной, поскольку в ней реализуются две фазы: распределение и слияние.