Здесь, как и в разделе 5.4.4, Аг и Dr применяются для обозначения соответственно восходящих и нисходящих серий относительгюй длины г. При использовании рассматриваемого метода сначала начальные серии по одной записываются на каждую из четырех лент и сливаются (чтение выполняется в обратно.м направлении) на пятую ленту. Затем распределение возобновляется, на этот раз циклически сдвинутое на одну позицию вправо по отношению к лентам, и в результате второго слияния образуется еще одна серия Di. Когда этим способом будут сформированы четыре серии Di, дополнительное слияние приведет к созданию Aie- Процесс можно продолжать, создав еще три Aie, слив их в Dei, и так до тех пор, пока не исчерпаются исходные данные. При этом заранее знать длину исходных данных не нужно.

Если число начальных серий 5 есть 4"*, то нетрудно заметить, что этот метод обрабатывает каждую запись ровно т + 1 раз (один раз во время распределения и тп раз во время слияния). Если 5 лежит между 4"" и 4™, можно с помощью фиктивных серий увеличить S до 4"*; следовательно, весь процесс сортировки потребует 11о§4 5 + 1 проходов по всем данным. Это именно то, что достигается при сбалансированной сортировке на восьми лентах. В общем случае осциллирующая сортировка с Г рабочими лентами эквивалентна сбалансированному слиянию с 2(Г -1) лентами, так как при этом выполняется [logj i 5] + 1 проходов по данным. Если 5 оказывается степенью Т - I, то это самое лучшее, что можно получить при любом методе с Г лентами (здесь достигается нижняя оценка из соотношения 5.4.4-(9)). С другой стороны, если 5 равно (Г - 1)™" + 1, т. е. ровно на единицу больше степени Т - 1, при этом методе теряется почти целый проход.

В упр. 2 показано, как, используя специальную программу завершения, устранить часть этой лишней работы для случая, когда S - не степень Т. Еще одно усовершенствование было предложено в 1966 году Деннисом Л. Бенчером (Dennis L. Bencher), который назвал свою процедуру перекрестным слиянием. [См.

Еще один подход к сортировке методом слияния был предложен Шелдоном Собелем (Sheldon Sobel) в JACM 9 (1962), 372-375. Вместо того чтобы начинать с распределения прохода, когда все начальные серии распределяются по лентам, он предложил алгоритм, который переключается то на распределение, то на слияние, так что большая часть сортировки происходит еще до того, как вся исходная информация полностью проанализирована.

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

Н. Wedekind, Datenorganisation (Berlin: W. de Gruyter, 1970), 164-166; см. также и. S. Patent 3540000 (1970).] Основная идея состоит в том, чтобы отложить слияние до тех пор, пока не будет накоплено больше сведений о 5. Мы обсудим несколько измененную форму первоначальной схемы Бенчера.

Этот усовершенствованный метод осциллирующей сортировки действует следующим образом.

В этот момент слияние всех Di в Ai не выполняется (если только не окажется, что исходные данные исчерпаны). Лишь после того, как закончится

Фаза 15 Слияние DiDi DiDi D4D4 Di - 4,

будет получена первая серия Л16

Фаза 16 Слияние Di Di Di ~ Аи 16. Вторая серия Aie появится после создания еще трех Di,

Фаза 22 Слияние D4D4 D4D4 Di - AieDi 4

Фаза 23 Слияние Di Di - Aie Aie 16,

и т. д. (ср. с фазами 1-5). Преимущества схемы Бенчера можно видеть, если имеется, например, только пять начальных серий: осциллирующая сортировка (ее модификация из упр. 2) выполняла бы четырехпутевое слияние (на фазе 2), за которым следовало бы двухпутевое слияние с общей стоимостью 4-1-4+1+5 = 14, тогда как схема Бенчера выполняла бы двухпутевое слияние (на фазе 3), за которым следовало бы четырехпутевое слияние с общей стоимостью 4 + 1 + 2 + 5 = 12. Оба метода также требуют небольших дополнительных затрат, а именно - однократной перемотки перед окончательным слиянием.

Точное описание метода Бенчера содержится ниже, в алгоритме В. К сожалению, соответствующую процедуру, по-видимому, трудней понять, чем запрограммировать; легче объяснить данный метод компьютеру, чем программисту! Частично это происходит по той причине, что рекурсивный метод выражен в итеративном виде и затем подвергнут некоторой оптимизации; читатель, возможно, обнаружит, что приходится несколько раз проследить за работой алгоритма, прежде чем станет понятно, что же происходит.

Алгоритм В (Осциллирующая сортировка с "перекрестным" распределением). Этот алгоритм берет первоначальные серии и распределяет их по лентам, время от времени прерывая процесс распределения, чтобы слить содержимое некоторых

лент (рис. 77). В алгоритме используется Р-путевое слияние ипредполагается, что имеется Г = Р + 1 > 3 накопителей на магнитной ленте (НМЛ) (не считая устройства, которое может применяться для хранения исходных данных). НМЛ должны допускать чтение как в прямом, так и в обратном направлениях; они обозначены числами 0,1,..., Р. Используются следующие массивы.

DCj] ) О < j < Р : Число фиктивных серий, наличие которых предполагается в конце j-й ленты

А[/, j], О < / < L, Здесь L - достаточно большое число, такое, что будет введено О j Р"*" начальных серий. Если А[/, j] = А; > О, то на ленте j имеется серия номинальной длины Р*, соответствующая "уровню /" работы алгоритма. Эта серия - восходящая, если к четно, и нисходящая, если к нечетно. А[, j] < О означает, что на уровне / лента j не используется

Инструкция "Записать начальную серию на ленту j" является сокращенным обозначением следующих действий.

Установить А[/, j] 0. Если исходные данные исчерпаны, то увеличить D[j] на 1; впротивном случае записать серию на ленту j (в порядке возрастания).

Инструкция "Произвести слияние на ленте j" используется как краткое обозначение следующих действий.

Если 0[г] > О для всех i ф j, то уменьшить D[i] на 1 при всех i ф j и увеличить D[j] на 1. В противном случае произвести слияние одной серии на ленте j со всех лент г ф j, таких, что D[i] = О, и уменьшить 0[г] на 1 для всех остальных

В2. Ввод завершен

. ВЗ. Начать новый уровень

ли выполнять \с:лияние?у/

Завершен(Г\

ли формиро-

Рис. 77. Осциллирующая сортировка с "перекрестным" распределением.

81. [Начальная установка.] Установить D[j] О при О < j < Р. Установить

А[0,0] •(--1, ; О, 9 0. Затем записать начальную серию на ленту j для

1 < j < Р.

82. [Ввод завершен?] (В этот момент лента q пуста и всякая другая лента содержит максимум одну серию.) Если еще есть исходные данные, перейти к шагу ВЗ. Однако если ввод исчерпан, то перемотать все ленты j ф q, такие, что А[0, j] четно; затем выполнить слияние на ленту q, читая все только что перемотанные