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

Иными словами, каждой схеме слияния соответствует схема распределения и каждой схеме распределения соответствует схема слияния. По некотором размышлении это становится понятным. Рассмотрим сортировку методом слияния, делающую все наоборот, т. е. разделяющую окончательный выводной файл на подфайлы, которые, в свою очередь, разделяются на другие подфайлы, и т. д. Наконец, разделим файл на 5 серий. Подобная схема может применяться к лентам тогда и только тогда, когда допустима соответствующая схема распределения для поразрядной сортировки 5 ключей. Эта двойственность слияния и распределения почти точна; она не вьшолняется только в одном отношении: данные с вводной ленты должны сохраняться в разное время.

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

Если сравнить ее с поразрядной сортировкой, то очевидно, что оба метода имеют, в сущности, одну и ту же структуру, но обратны во времени и имеют обратное расположение содержимого на лентах: 123I (две серии длиной 1 каждая, за которыми следует одна серия длиной 3) соответствует {3,8,9}{4}{5} (два подфайла, содержа-пще по 1 ключу, перед которыми расположен один подфайл, содержащий 3 ключа).

Двигаясь в другую сторону, можно, в принципе, построить поразрядную сортировку, двойственную многофазному слиянию, каскадному слиянию и т. д. Например, многофазному слиянию 21 серии на трех лентах, изображенному в начале раздела 5.4.2, соответствует следующая интересная поразрядная сортировка.

Фаза Т1 Т2 ТЗ

{0,1,...,20} - -

1 - {0,2,4,5,7,9,10,12,13,15,17,18,20} {1,3,6,8,11,14,16,19}

(".""»> - !й:?:?:1йг:)5;52!

4 - {3,8,16}{4,9,17}{5,10,18} ЮпгЛнМгп;

* {6,11,19}{7,12,20} {0,13}{1,14}{2,15}

{8}{9}{10}{11}{12} -

6 {8}{9}{10}{11}{12}{13}...{20} {0}{1}...{7} -

Правило распределения, согласно которому ключи располагаются на лентах на каждом шаге, кажется магическим, но на самом деле оно имеет простую связь с системой счисления, использующей числа Фибоначчи! (См. упр. 2.)

Обратное чтение. Двойственность поразрядной сортировки и слияния применима также к алгоритмам, читающим ленту в обратном направлении. Мы определили Т-lifo-деревья в разделе 5.4.4, и нетрудно видеть, что они подходят для поразрядной сортировки в той же мере, что и для сортировки методом слияния.

Поразрядная сортировка с обратным чтением была фактически рассмотрена Джоном Мочли (John Mauchly) еще в 1946 году в одной из первых опубликованных работ по сортировке вообще (см. раздел 5.5). Мочли на самом деле предложил следующую схему сортировки.

Фаза Т1 Т2 ТЗ Т4

- {0,1,2,..,,9} - -

1 {4,5} - {2,3,6,7} {0,1,8,9}

2 {4,5}{2,7} {3,6} - {0,1,8,9}

3 {4,5}{2,7}{0,9} {3,6}{1,8} - -

4 {4,5}{2,7} {3,6}{1,8} {9} {0}

8 - •9}8}{7}{6}{5} {0}{1}{2}{3}{4}

С - - - {0}{1}{2}{3}{4}{5}...{9}

Эта схема не является салюй эффективной среди всех возможных, но она интересна тем, что показывает: методы с частичными проходами рассматривались применительно к поразрядной сортировке еще в 1946 году, хотя в литературе по слиянию они появились лишь около 1960 года.

Эффективная конструкция схем распределения с обратным чтением была предложена в работе А. Bayes, САСМ 11 (1968), 491-493. Пусть дано Р + I лент и 5 ключей; разделите ключи на Р подфайлов, каждый из которых содержит [5/PJ или {5/Р] ключей, и примените эту процедуру рекурсивно к каждому подфайлу. Если 5 < 2Р, то один подфайл должен состоять из единственного наименьшего ключа; его и следует записать на выводную ленту. (Общая конструкция с прямым порядком Р. М. Карпа, описанная в конце раздела 5.4.4, включает этот метод как частный случай.)

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

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

новляется. Например, если имеются три рабочие ленты и одна выводная и если ключи являются двоичными числами, мы можем сначала поместить ключи вида Ох на ленту Т1, а ключи 1х - на ленту Т2. Если на ленте Т1 больше записей, чем может поместиться в памяти, то вновь просматриваем ее и помеш,аем ООх на Т2 и 01х на ТЗ. Теперь, если подфайл ООх достаточно короткий, выполняем его внутреннюю сортировку, выводим результат, а затем начинаем обработку подфайла Ola;. Подобный метод был назван Э. X. Фрейдом каскадной псевдопоразрядной сортировкой [JACM 3 (1956), 157-159]; более подробно его разработали X. Нэглер (Н. Nagler) [JACM 6 (1959), 459-468], который дал ему красочное название - "метод двуглавого змия", и Ч. X. Годетт (С. Н. Gaudette) [IBM Tech. Disclosure Bull. 12 (April, 1970), 1849-1853].

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

Для внешней поразрядной сортировки существует, однако, одно важное применение. Предположим, например, что и.меется файл, содержащий фамилии всех сотрудников большого предприятия в алфавитном порядке. Предприятие состоит из десяти отделений, и требуется рассортировать файл по отделениям, сохраняя алфавитный порядок сотрудников каждого отделения. Если файл длинный, значит, сложилась именно та ситуация, в которой следует применять стабильную поразрядную сортировку, так как число записей, принадлежащих каждому из отделений, будет, вероятно, больше числа записей, которые были бы в начальных сериях, полученных методом выбора с замещением. Вообще говоря, если диапазон ключей так мал, что набор записей с одинаковыми ключами более чем вдвое превышает объем оперативной памяти, то разумно использовать поразрядную сортировку.

Мы видели в разделе 5.2.5, что на некоторых высокоскоростных компьютерах внутренняя поразрядная сортировка предпочтительнее слияния, поскольку "внутренний цикл" поразрядной сортировки обходится без сложных переходов. Если внешняя память очень быстрая, то для таких машин может оказаться проблемой выполнение слияния данных с такой скоростью, чтобы поспеть за оборудованием ввода-вывода. Поэтому в подобной ситуации поразрядная сортировка, возможно, лучше слияния, особенно если известно, что ключи распределены равномерно.

УПРАЖНЕНИЯ

1. [20] В начале раздела 5.4 было определено общее сбалансированное слияние на Т лентах с параметром Р, 1 < Р < Т. Покажите, что оно соответствует поразрядной сортировке, использующей систему счисления со смешанным основанием.