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

проходе 8 серий сливаются на f6; в конце работы на /2 содержится отсортированное множество элементов ( рис. 2.15).

Многофазная сортировка более эффективна, чем сбаля сированная сортировка, поскольку, если даны N лент, q всегда имеет дело с (N-1)-путевым слиянием вместодгл путевого слияния. Поскольку число требующихся проходГ, приблизительно равно logArn, где п - число сортируемых эл-ментов, а N - число входных лент для слияния, многофз^ ный метод обещает дать значительное улучшение по сравни нию со сбалансированным слиянием.

Разумеется, в приведенных примерах было тщатепьн подобрано распределение начальных серий. Для того чтоб; узнать, какие исходные распределения серий требуются дл правильной-работы алгоритма, мы пойдем обратным путец начиная с окончательного распределения (последняя строк на рис. 2.15). Переписывая таблицы для этих двух примере и поворачивая каждый ряд на одну позицию по отношенк к предыдущему ряду, мы получаем табл. 2.13 и 2.14 да шести проходов и для трех и шести лент соответственно.

Таблица 2.18.: Идеальное распределение )

серий на двух лентах

Таблица 2.14. Идеальное распределение серий на пяти лентах

Из табл. 2.13 можно вывести соотношения

Л для/>0 (2-*

(0)==1, 4 * -О- Полагая a\ = f, мы получаем

h+i = fi + fi-u для .

/, = 1, (2.41)

/о==0.

q Р рекурсивные правила (или рекуррентные соотноше-0л), определяющие так называемые числа Фибоначчи:

\ 1, 1, 27 3,8, Гз 21. 34, 55.....

Каждое число Фибоначчи представляет собой сумму двух предшествующих чисел. Итак, для того, чтобы многофазный метод с тремя лентами работал правильно, числа начальных серий на двух входных лентах должны быть двумя соседними Б ряду Фибоначчи. А что можно сказать относительно второго примера (табл. 2.14) с шестью лентами? Правила построения чисел легко записать в таком виде:

а+п = + 4) = а(0 + a\t- .

(;+!) а(/ + аа) = а(0 + а</-) + а(/-2), . 2.42)

Подстановка вместо а[ дает

fi+i = fi + /i-i + /i-2 + /i-3+fi-4 для г>4, /4=1. (2.43)

/г = О для I < 4.

Эти числа являются так называемыми числами Фибоначчи порядка 4. В общем виде числа Фибоначчи порядка р определяются следующим образом:

ff= 1. (2.44)

= О для 0<i<p.

Заметим, что обычные числа Фибоначчи имеют порядок 1.

Теперь мы убедились, что исходные числа серий для Деальной многофазной сортировки с п лентами должны Ыть суммами п-1, п - 2, 1 (см. табл. 2.15) последовательных чисел Фибоначчи порядка п - 2. Из этого сле-%ет, что алгоритм многофазного слияния применим только аким входным данным, в которых число серий есть сумма

Таблица 2.15. Количество серий, при которых возможно идеальное распределение

п - 1 таких сумм Фибоначчи. Итак, возникает важный во-) прос: что делать, если число начальных серий не является такой идеальной суммой? Ответ прост (и типичен для подобных ситуаций): мы предполагаем существование гипотетических пустых серий, таких, что сумма реальных и гипотети- ческих серий дает идеальную сумму. Пустые серии называются фиктивными сериями. Но этот ответ на самом деле неудовлетворителен, так как сразу вызывает следующий, более трудный вопрос: как распознаются фиктивные серии пр слиянии? Перед тем как ответить на него, мы вернемся к упомянутой выще проблеме распределения действительных и фиктивных серий на п - 1 лентах.

Однако, для того чтобы найти подходящее правило распределения, мы должны знать, как сливаются настоящие и фиктивные серии. Ясно, что выбор фиктивной серии с ленты означает, что £-я лента не участвует в слиянии; в р^ зультате слияние происходит с менее чем п - I лент. Слияние фиктивных серий со всех п - 1 входных лент не предполагает никакой действительной операции слияния, а означает прост* запись фиктивной серии на выходную ленту. Из этого можВ