Фибоначчиево слияние

В действительности, можно полностью устранить копирование, если начать с f_n отрезков в файле F1 и f_n-1 отрезков в F2, где f_n и
f_n-1 – последовательные числа Фибоначчи. Таблица, приведенная ниже, поясняет процесс слияния. Элемент таблицы вида A*Bобозначает А отрезков относительной длины В.

Суммарное число проходов по данным составит , в то время, как двухфазная процедура затратила бы 8 проходов. Эту идею можно обобщить на N входных файлов, используя N-1 –путевое слияние. В качестве примера рассмотрим случай N=6 при числе начальных отрезков 129.

Чтобы метод работал, необходимо после каждой фазы иметь точное "фибоначчиево" распределение отрезков по файлам. Для этого некоторые файлы можно дополнить фиктивными отрезками нулевой длины. Точное фибоначчиево распределение можно получить, прокручивая рассмотренную схему в обратном порядке, циклически переставляя содержимое файлов и игнорируя выходной файл. При N=6 имеем следующее распределение отрезков:

Из приведенной таблицы следует, что

e_n=a_n-1
d_n=a_n-1+e_n-1=a_n-1+a_n-2
c_n=a_n-1+d_n-1=a_n-1+a_n-2+a_n-3
b_n=a_n-1+c_n-1=a_n-1+a_n-2+a_n-3+a_n-4
a_n=a_n-1+b_n-1= a_n-1+a_n-2+a_n-3+a_n-4+a_n-5,

где a₀=1 и a_n=0 при n<0.

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

при n ³ p,

при 0 £ n £ p-2, =1.

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

начальных отрезков для 1 £ k £ p, а общее количество начальных отрезков во всех файлах составит