Многофазное слияние. Внешняя сортировка.

Числа Фибоначи – это последовательность, начинающаяся с двух единиц, а каждое последущее равно сумме двух предыдущих.

Если в двух исходных файлах получить количество упорядоченых последовательностей равных двум соседним числам Фибоначи (например, 5 отрезков в одном и 8 в другом), то используя три файла мы сможем завершить сортировку не прибегая к дополнительному разделению файлов на два.

Принцип:

Подбираем длину цепочки таким образом, что бы хватило памяти на сортировку цепочки. И так что бы количество отрезков было равно какому то числу Фибоначи. Тогда распределяем их в количество совпадающих с двумя предыдущими числами Фибоначи.

Алгоритм:

Сливаем в один файл на каждом шаге до тех пор, пока один из входных не закончится. При этом второй буедт содержать еще какое то количество цепочек. Тот файл который опустел объявляем выходным, а выходной становится входным. И продолжаем снова до тех пор, пока один не станет  полным, а два других пустыми.

Числа Фибоначи гарантируют, что это произойдет без эксцессов.