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

Каскадное слияние преобразуется таким же способом. Рассмотрим, например, сортировку 14 начальных серий на четырех лентах.

Т1 Т2 ТЗ Т4

Проход 1 AiAiAiAiAiAi AiAiAiAiAi AiAiAi -

Проход 2 - Dl D2D2 D3D3D3

Проход 3 Аб Аь Аз -

Проход 4 - - - Du

Как и ранее, можно получить Ац вместо Dn, если перемотать Т1, Т2, ТЗ непосредственно перед последним проходом. Заметим, что это "чистое" каскадное слияние в том смысле, что все однопутевые слияния выполнены явным образом. Если бы мы запретили операции копирования, как в алгоритме 5.4.3С, то после второго прохода столкнулись бы с ситуацией

Ai - D2D2 D3D3D3

В этом случае невозможно продолжать работу, используя трехпутевое слияние, так как нельзя сливать серии противоположных направлений! Можно было бы избежать копирования Т1 на Т2, если перемотать Т1 и начать ее считывание в прямом направлении на следующей фазе слияния (в то время как ТЗ и Т4 читаются в обратном направлении). Но тогда пришлось бы вновь перемотать Т1 после слияния, так что данный прием заменяет одно копирование двумя перемотками.

Таким образом, метод распределения алгоритма 5.4.3С при обратном чтении не столь эффективен, как при прямом чтении; временные затраты резко возрастают каждый раз, когда число начальных серий проходит через "точное" каскадное распределение. Чтобы получить более "гладкий" переход между точными каскадными распределениями, можно использовать иной метод распределения (см. упр. 17).

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

Т1 Т2 ТЗ

Фаза 1 AiAiAiAiAi AiAiAiAiAiAiAiAi -

Фаза 2 - AiAiAi D2D2D2D2D2

Здесь мы оказываемся в тупике; можно было бы перемотать Т2 или ТЗ и затем читать их в прямом направлении, в то время как остальные ленты - в обратном. Но это значительно запутало бы дело и преимущества от обратного чтения были бы невелики.

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

Таким образом, на Т1 всегда помещается нечетное число серий, тогда как на ленты с Т2 по Т5 - четные числа (в порядке убывания, чтобы упростить присвоение фиктивных серий). Такое распределение имеет то преимущество, что окончательная выводная лента известна заранее независимо от числа начальных серий, которые придется обрабатывать. Оказывается (см. упр. 3), что если используется эта схема, то результат всегда будет находиться на Т1 в порядке возрастания.

Фаза 1 AiDiAxDiAi DiAiDiAiDiAiDiAi -

Фаза 2 - DiAiDi D2A2D2A2D2

Фаза 3 A3D3A3 - D2A2

Фаза 4 Аз D5A5 -

Фаза 5 - Ds Dg

Фаза 6 Лхз - -

Этот принцип был кратко упомянут Р. Л. Гилстадом (R. L. Gilstad) в его ранней статье о многофазном слиянии. Более полное описание приводится в САСМ 6 (1963), 220-223.

Рассматриваемый ADA.. .-метод прекрасно подходит для многофазного слияния с любым числом лент; можно показать, что Аи D согласуются соответствующим образом на каждой фазе, но только при условии, что на начальном проходе чередующиеся серии А и D должны быть сформированы на каждой ленте и что каждая лента заканчивается серией А (или каждая лента заканчивается серией D). Так как последняя серия, записываемая в файл вывода во время одной фазы, имеет направление, противоположное направлению последней использованной серии из файла ввода, то и на следующей фазе серии всегда будут иметь надлежащую ориентацию. Далее, как в упр. 5.4.2-13, большинство точных фибоначчиевых распределений требует нечетного числа серий на одной ленте (окончательной выводной ленте) и четного числа серий на всех остальных лентах. Если Т1 предназначена для вывода конечного результата, значит, можно гарантировать, что все ленты будут заканчиваться серией А, если ленту Т1 начнем с А, а все остальные ленты - с D. Можно использовать метод распределения, аналогичный алгоритму 5.4.2D, изменив его таким образом, чтобы распределение на каждом уровне имело в качестве выводной ленту Т1. (Мы пропускаем уровни 1, Т+1, 2Т+1, ..., так как на них окончательной выводной лентой является первоначально пустая лента.) Например, в случае для шести лент вместо 5.4.2-(1) можно использовать следующее распределение серий.

Окончательная

Другой способ распределения для многофазной схемы с обратным чтением был предложен в статье D. Т. Goodwin, J. L. Venn, САСМ 7 (1964), 315. Можно распределять серии, почти как в алгоритме 5.4.2D, начиная с D-серии на каждой ленте. Когда ввод исчерпан, мы представляем себе фиктивную Л-серию расположенной в начале единственной "нечетной" ленты, если только не достигнуто распределение со всеми нечетными числами. Остальные фиктивные серии мы представляем себе расположенными в конце лент или сгруппированными в пары в середине. Вопрос об оптимальном размещении фиктивных серий анализируется ниже, в упр. 5.

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

Для начала необходим более удобный способ описания схем слияния вместо довольно таинственных таблиц "содержимого лент", которые использовались выше. Карп предложил два таких способа - векторное представление схемы слияния и представление в виде дерева. Оба представления можно с успехом использовать, и мы опишем их по очереди.

Векторное представление схемы слияния состоит из последовательности "векторов слияния" ... у у°\ каждый из которых имеет Т компонент; у изображает г-й с конца шаг слияния следующим образом:

{+1, если лента с номером j является вводной для данного слияния; О, если лента с номером j не используется в данном слиянии; (2) - 1, • если на ленту с номером j выводится результат данного слияния.

Таким образом, ровно одна компонента j/*) равна -1, остальные компоненты равны О и 1. Итоговый вектор у° - особый: это единичный вектор, имеющий 1 в позиции j (если окончательный рассортированный результат оказывается на устройстве j) и О в остальных позициях. Из данного определения следует, что векторная сумма

v() = + + + (3)

представляет собой распределение серий на лентах непосредственно перед г-м с конца шагом слияния; причем на ленте j находится uj* серий. В частности, по v" можно судить, сколько серий помещается на каждую ленту на начальном проходе распределения.

Три схемы слияния, описанные ранее в этом разделе в табличной форме, имеют следующие векторные представления.