Пример 7. Многофазное слияние с обратным чтением. В этом примере используется только пять лент из шести, чтобы устранить время перемотки и смены вводной ленты. Таким образом, применяется только четырехпутевое слияние и такая же структура буферов, как в примерах 4 и 5. Используется распределение, аналогичное приведенному в алгоритме 5.4.2D, но направление серий чередуется и лента 1 фиксируется, как конечная выводная лента. Сначала записывается восходящая серия на ленту 1, затем - нисходящие серии 2-4, после этого - восходящие серии на ленты 2-4, нисходящие серии на ленты 1-3 и т. д. Всякий раз, когда переключается направление, выбор с замещением обычно дает более короткую серию, поэтому было образовано 77 начальных серий вместо 72 в примерах 4 и 5.

Эта процедура в результате дает распределение (22, 21, 19, 15) серий, а ближайшее точное распределение - (29, 56, 52, 44). В упр. 5.4.4-5 показано, как построить строки чисел слияния, которые могут использоваться для размещения фиктивных серий оптимальным образом. Такая процедура может выполняться на практике, поскольку конечность бобины гарантирует, что 5-никогда не будет слишком большим. Поэтому пример на диаграмме А был построен с использованием такого метода размещения фиктивных серий (см. упр. 7). Он оказался самым быстрым из всех представленных примеров.

Пример 8. Каскадное слияние с обратным чтением. Как и в примере 7, здесь участвует только 5 лент. Эта процедура соответствует алгоритму 5.4.ЗС, используя перемотку и прямое чтение, чтобы избежать однопутевого слияния (так как перемотка более чем в два раза быстрее чтения на устройствах MIXT). Распределение, следовательно, то же, что и в примере 6. Используя символ "4-" для обозначения перемотки, изобразим эту схему так;

Л?! AY> -

AU AU - D\DlDl Df

- Dn Agi D25 D21

Л72 - - - -

Пример 9. Осциллирующая сортировка с обратным чтением. При осциллирующей сортировке с Г = 5 (алгоритм 5.4.5В) может использоваться распределение буферов, как в примерах 4, 5, 7 и 8, поскольку она выполняет четырехпутевое слияние. Однако выбор с замещением действует здесь иначе, так как непосредственно перед входом в каждую фазу слияния выводится серия длиной 700 (а не примерно 1 400), чтобы очистить внутреннюю память. Следовательно, здесь порождается 85 серий вместо 72. Некоторые ключевые шаги этого процесса таковы:

- Al А1А1 А1А1 А1А1

d4 - Al Al Аг

DiDi DiDi DiDi Di -

Di Di Di - A16

Пример 10. Осциллирующая сортировка с прямым чтением. В последнем примере выбор с замещением не используется, так как все начальные серии должны быть одной длины. Следовательно, будет происходить внутренняя сортировка 1 ООО записей (полной емкости памяти) каждый раз, когда требуется начальная серия; это дает 5 = 100. Вот некоторые ключевые шаги процесса:

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

Оценка времени выполнения. Посмотрим теперь, как вычислить приблизительное время выполнения некоторого метода сортировки с учетом характеристик используемого НМЛ MIXT. Можно ли предсказать результаты, изображенные на диаграмме А, не выполняя детального моделирования?

20 50 100 200 Начальные серии, S

Сбалансированная (Г = 6) Каскадная (Г = 5) Многофазная (Г = 5)

Осциллирующая (Г = 5)

500 1000 2000 5000

Рис. 85. Несколько обманчивый способ сравнения схем слияния.

Один способ, который традиционно использовался для сравнения различных схем слияния, состоит в том, чтобы совместить графики, подобные представленным на рис. 70, 74 и 78. На этих графиках изображено эффективное число проходов по данным как функция от числа начальных серий в предположении, что все начальные серии имеют примерно равную длину (рис. 85). Но это не позволяет выполнить адекватное сравнение, потому что, как мы видели, разные методы приводят к различному числу начальных серий; кроме того, имеются различные накладные расходы, зависящие от относительной частоты междублочных промежутков; значительное воздействие оказывает также время перемотки. Все эти зависящие от конкретного оборудования особенности затрудняют использование машинно-независимой методики истинного сравнения методов слияния. С другой стороны, из рис. 85 все же явствует, что за исключением сбалансированного слияния эффективное число проходов может быть достаточно хорошо аппроксимировано плавными кривыми вида alnS + p. Следовательно, можно неплохо сравнивать методы в любой практической ситуации, проанализировав формулы, аппроксимирующие время вьшолнения. Конечно, наша цель - найти формулы простые, но достаточно близкие к реальности.

Попытаемся теперь вывести такие формулы в терминах следующих параметров:

Л - число сортируемых записей, С - число символов в записи,

М - объем доступного пространства в оперативной памяти (символов; предполагается кратным С)

т - время в секундах, нужное для того, чтобы прочитать или записать один символ,

рт время в секундах для перемотки в пересчете на один символ, ат - время в секундах стартстопной задержки, 7 - число символов в междублочном промежутке.