Многофазная сортировка.

В основе данной сортировки лежит отказ от жесткого понятия прохода и разделения файлов на две категории. Рассмотрим этот метод сортировки на примере:

Если , то

.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…

f1	f2	f3		L			
13	8	0	L=6	0	1	0	1
5	0	8	L=5	1	1	1	2
0	5	3	L=4	2	2	1	3
3	2	0	L=3	3	3	2	5
1	0	2	L=2	4	5	3	8
0	1	1	L=1	5	8	5	13
1	0	0	L=0	6	13	8	21

Таким образом, необходимо, чтобы числа начальных серий в двух входных последовательностях были двумя соседними числами Фибоначчи.

f1	f2	f3	f4	f5	f6		L						
16	15	14	12	8	0	L=5	0	1	0	0	0	0	1
8	7	6	4	0	8	L=4	1	1	1	1	1	1	5
4	3	2	0	4	4	L=3	2	2	2	2	2	1	9
2	1	0	2	2	2	L=2	3	4	4	4	3	2	17
1	0	1	1	1	1	L=1	4	8	8	7	6	4	33
0	1	0	0	0	0	L=0	5	16	15	14	12	8	65

;

;

;

;

.

Подставляя вместо , получаем

(для i  4);

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

(для i > p); .

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

Теперь уже ясно, что исходные числа серий для идеальной многофазной сортировки с N последовательностями (файлами) представляют собой последовательность чисел Фибоначчи порядка N – 2. Отсюда следует, что метод применим для лишь входов, сумма серий на которых есть сумма N – 1 таких чисел Фибоначчи. В том случае, когда сумма серий отличается от идеальной суммы, то вводим фиктивную серию.