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

Забудем на некоторое время о фиктивных сериях и рас-лотрим задачу распределения неизвестного числа серий на 1 лент. Ясно, что в процессе распределения можно полу-qarb чнсла-Фибеначчи порядка п - 2, определяющие желательные количества серий на каждой ленте. Предположив, например, что п = 6, и ссылаясь на табл. 2.14, мы начинаем q распределения серий, указанных в строке с номером /= 1(1, 1, 1, I. 1); если имеются еще серии, мы переходим ко второй строке (2, 2, 2, 2, 1); если входные данные еще не исчерпаны, распределение производится в соответствии со следующей строкой (4, 4, 4, 3, 2) и т. д. Номер строки мы будем называть уровнем. Очевидно, что чем больше число серий, тем выше будет уровень чисел Фибоначчи, который в данном случае равен количеству проходов, или переключений лент, необходимых для последующей сортировки.

Алгоритм распределения теперь, в первом приближении, можно сформулировать следующим образом:

1. Пусть перед нами стоит цель - числа Фибоначчи порядка п - 2, уровня 1.

2. Распределяем серии согласно поставленной цели.

3. Если цель достигнута, вычисляем следующий уровень чисел Фибоначчи; разность между числами этого уровня и числами предыдущего уровня представляет собой новую цель распределения. Возвращаемся к шагу 2. Если цели нельзя достичь, потому что входные данные исчерпаны, распределение заканчивается.

Правила вычисления следующего уровня чисел Фибоначчи содержатся в их определении (2.44). Итак, мы можем со-<редоточить внимание на ш'аге 2, где при заданной цели последовательные серии должны распределяться поочередно Ц п--\ лент. Именно здесь в наших рассуждениях должны вновь появиться фиктивные серии.

Предположим, что, повышая уровень, мы записываем следующую цель с помощью разностей di для i=l, n-l, где di обозначает число серий, которые на данном Hiare нужно отправить на ленту L Теперь можно считать, 0 Мы сразу помещаем dt фиктивных серий на ленту i и рас-Матриваем последующее распределение как замену фиктив-Ых серий действительными так, что при каждой замене di Уменьшается на 1. Таким образом, di будет указывать число фиктивных серий на ленте i, когда входные данные будут Черпаны.

2. Сортировка

Неизвестно, какой алгоритм дает оптимальное распред„ ление, но следующий, предлагаемый нами метод оказал очень хорошим. Он называется горизонтальным pacnpeQ лением (см. [2.7], т. 3, стр. 322); этот термин становится цц нятным, если представить себе серии сложенными в випр пирамиды, как показано на рис. 2.16 для п = 6 уровня r (см. табл. 2.14).

Для того чтобы получить равномерное распределение оставшихся фиктивных серий как можно более быстрым спо. собом, при замене их на действительные уменьшается высота пирамиды: фиктивные серии берутся с горизонтальных уров. ней слева направо. При таком способе серии распределяют-ся на ленты в последовательности, указанной числами на 4)ис. 2.Ш.

Рис. 2.16. Горизонтальное распределение серий.

Теперь мы можем описать алгоритм в виде процедуры, называемой selecttape, которая вызывается каждый раз, когда переписана какая-либо серия и нужно выбрать ленту, с которой берется очередная серия. Мы предполагаем, что существует переменная /, обозначающая индекс текущей бИ\ ходной ленты. Переменные а, и Ф обозначают числа идеала ного и фиктивного распределений для ленты i:

J: tapeno;

a,d: array [tapend\ of index; level: integer

(2.46)

Эти переменные инициируются следующими значениями:

ai = l, di = \ для 1=1 ...п~\, й„ = О, (i = О (фиктивные),

level = 1.

Отметим, что selecttape должна вычислять следующую строй табл. 2.14j т. е. значения ... , а'Др каждый раз при ув

НИИ уровня. В это же время вычисляется также очеред-Ji4jjgj[b , т. е. разности d - Sp- q~*- Приведенный/Элго- основан на том, что результирующее значение di умень-ется при увеличении номера строки (ведущие вниз ступени рис. 2.16). (Отметим, что исключением является переход ровня О на уровень 1; следовательно, этот алгоритм дол- gg использоваться, начиная с уровня 1.) Selecttape закан-ивает работу, уменьшая d/ на 1; это соответствует замене фиктивной серии на ленте у действительной серией:

procedure selecttape;

var /: tapeno; z\ integer;

if 4/1 < 47+1] then i := j+1 else begin if d[j] = 0 then

bein level := level + I; z := a[l];

#for / := 1 to И-1 do begin d[q := z+a[i+l]~a[i\; аЩ := z+ali+1] end end ;

./ := 1 nd ;

dU] := ~1

Предполагая, что у нас есть процедура для переписи серии с /О на /[/], мы можем записать начальную фазу распределения следующим образом (как обычно, считаем, что на входе имеется по крайней мере одна серия):

repeat selecttape, соругип

until eofifO)

Но здесь мы должны остановиться и вспомнить эффект, который наблюдался при распределении серий в рассмотренном Р^нее алгоритме естественного слияния: из-за того, что две серии, последовательно записанные на одну ленту, могут образовать одну серию, реальное количество серий на лентах Чожет не совпасть с ожидаемым. Когда алгоритм сортировки Разрабатывался таким образом, что его работа не зависела Количества серий, этот побочный эффект можно было Покойно игнорировать. Но при многофазной сортировке мы еобенно заботимся о том, чтобы знать точные количества ,Рий на каждой ленте. Следовательно, нам приходится учи-Вать возможность такого случайного слияния. Поэтому нельзя избежать нового усложнения алгоритма Определения. Оказывается необходимым сохранять ключ