Число проходов по всем данным сократилось до "lg5] + , так как на шагах A3 и А5 выполняется только "половина прохода", т. е. сэкономлено около 25% времени.

В действительности можно даже полностью устранить копирование, если начать с Fn серий на ленте Т1 и Fn-i серий на Т2, где F„ и F„ i - последовательные числа Фибоначчи. Рассмотрим, например, случай, когда п = 7, 5 = F„ 4- Fn-i = 13 4-8 = 21.

Фаза Содержимое Содержимое Содержимое Примечание

Т1 Т2 ТЗ

1 1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1 Начальное распределение

2 1,1,1,1,1 - 2,2,2,2,2,2,2,2 Слияние 8 серий на ТЗ

3 - 3,3,3,3,3 2,2,2 Слияние 5 серий на Т2

4 5,5,5 3,3 - Слияние 3 серий на Т1

5 5 - 8,8 Слияние 2 серий на ТЗ

6 - 13 8 Слияние 1 серии на Т2

7 21 - - Слияние 1 серии на Т1

Здесь "2,2,2,2,2,2,2,2", например, обозначает восемь серий относительной длины 2, если считать относительную длину каждой начальной серии равной 1. Всюду в этой таблице присутствуют числа Фибоначчи!

Полный проход по данным осуществляется только на фазах 1 и 7; на фазе 2 обрабатывается лишь 16/21 от общего числа начальных серий, на фазе 3 - лишь 15/21 и т. д. Таким образом, суммарное число "проходов" равно (214-164-154-154-164-13 4- 21)/21 = 5, если предположить, что начальные серии имеют примерно равную длину. Для сравнения заметим, что рассмотренная выше двухфазная процедура затратила бы 8 проходов на сортировку этой 21 начальной серии. Мы увидим, что в общем случае данная схема Фибоначчи требует приблизительно 1.04 Ig 5 4-0.99 проходов, что делает ее сравнимой с четырехленточным сбалансированным слиянием, хотя она использует только три ленты.

Эту идею можно обобщить для Т лент при любом Т > 3, используя {Т - 1)-путевое слияние. Мы увидим, например, что для четырех лент требуется только около .703 Ig 54-0.96 проходов по данным. Обобщенная схема использует обобщенные числа Фибоначчи. Рассмотрим следующий пример с шестью лентами.

Здесь 1 обозначает 31 серию относительной длины 1 и т. д.; везде используется пятипутевое слияние. Эта общая схема была представлена в работе R. L. Gilstad, Ргос. Eastern Joint Computer Conf. 18 (1960), 143-148, в которой она названа многофазным слиянием. Случай для трех лент был открыт Б. К. Бетцем (В. К. Betz) [неопубликованная заметка, Minneapolis-Honeywell Regulator Co. (1956)].

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

ление" серий по лентам. Читая приведенную выше таблицу снизу вверх, можно заметить, что первые семь точных фибоначчиевых распределений при Г = 6 суть {1,0,0,0,0}, {1,1,1,1,1}, {2,2,2,2,1}, {4,4,4,3,2}, {8,8,7,6,4}, {16,15,14,12,8} и {31,30,28,24,16}. Теперь перед нами стоят следующие важные вопросы.

1. Какое правило скрыто за этими точными фибоначчиевыми распределениями?

2. Что делать, если S не соответствует фибоначчиевому распределению?

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

4. Сколько "проходов" по данным потребует Т-ленточное многофазное слияние (как функция от 5 - числа начальных серий)?

Мы обсудим эти четыре вопроса по очереди; сначала дадим "простые ответы" а затем займемся более глубоким анализом.

Точные фибоначчиевы распределения можно получить, "прокручивая" рассмотренную схему в обратном направлении и циклически переставляя содержимое лент. Например, при Г = 6 имеем следующее распределение серий.

(После начального распределения лента Т6 всегда будет пустой.)

Из правила перехода от уровня п к уровню п + 1 ясно, что условия

о„ > Ь„ > с„ > d„ > е„

выполняются на любом уровне. В самом деле, легко видеть из (1), что

е„ = о„ 1,

dn - ап-1 + е„ 1 = о„ 1 + о„ 2,

с„ = о„ 1 4- d„ i = о„ 1 4- о„ 2 4- о„ з,

Ьп = о„ 1 4- с„ 1 = о„ 1 4- о„ 2 4- о„ з 4- о„ 4,

о„ = о„ 1 4- Ьп-1 = о„ 1 4- о„ 2 4- о„ з 4- о„ 4 4- о„ 5,

где Оо = 1 и где мы полагаем, что о„ = О при п = - 1, -2, -3, -4.

Числа Фибоначчи р-го порядка определяются правилами

Fi) = Fi], + Fi% + ... + Fi% при n > p;

FP) = 0 при 0 < n < p - 2; = 1.

Другими словами, мы начинаем с р - 1 нулей, затем пишем 1 и каждое следующее число является суммой р предыдущих чисел. При р = 2 это обычная последовательность Фибоначчи; для больших значений р ее впервые изучил, по-видимому, В. Шлегель {V. Schlegel) в Ei Progreso Matematico 4 (1894), 173-174. Шлегель вывел производящую функцию

V Р(-)." = = (5)

" 1-2-2-----zP 1-22 + 2Р+1"

п>0

Формула (3) показывает, что число серий на Т1 в процессе шестиленточного многофазного слияния является числом Фибоначчи пятого порядка: о„ = F.

В общем случае, если положить Р = Т - 1, распределения в многофазном слиянии для Т лент будут аналогичным образом соответствовать числам Фибоначчи Р-го порядка. В точном распределении п-го уровня на к-й ленте будет

п+Р-2 + п+Р-3 + +

начальных серий для 1 < А; < Р, а общее количество начальных серий на всех лентах будет, следовательно, равно

tn = FPi:i> 2 + {Р- l)ii+l>-3 + --- + Fi-l (6)

Это решает вопрос о "точном фибоначчиевом распределении" Но что мы должны делать, если S не равно в точности t„ ни при каком п? Как первоначально поместить серии на ленты?

Если 5 не является точным числом Фибоначчи (а чисел Фибоначчи не так уж много), то можно действовать, как в сбалансированном Р-путевом ашянии, добавляя "фиктивные серии"; поэтому можно считать, что S, в конце концов, будет точным. Существует несколько способов добавления фиктивных серий, но мы еще не знаем, как это сделать наилучшим образом. В первую очередь, рассмотрим метод распределения серий и приписывания фиктивных серий, который хотя и не самый оптимальный, но зато достаточно простой и, по-видимому, лучше всех остальных методов такой же степени сложности.

Алгоритм D (Сортировка методом многофазного слияния с использованием "горизонтального" распределения). Этот алгоритм (рис. 68) берет начальные серии и распределяет их одну за другой по лентам, пока запас начальных серий не исчерпается. Затем он определяет, как необходимо сливать ленты, используя Р-путевое слияние, в предположении, что имеются Г = Р 4-1 > 3 накопителей на магнитной ленте. Ленту Т можно применять для хранения исходных данных, так как на нее не записывается ни одна начальная серия. В памяти хранятся следующие таблицы.

А Ijl, 1 < J < У: Точное фибоначчиево распределение, к которому мы стремимся

DCj]j 1 < J < - Число фиктивных серий, которые считаются присутствующими в начале ленты на логическом устройстве с номером j