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

Метод многофазной сортировки основан на том, что имеется несколько входных файлов с разным числом серий и только один выходной файл. При каждом проходе серии из входных файлов сливаются до тех пор, пока входной файл с наименьшим числом серий не будет исчерпан. Тогда освободившийся файл становится выходным, начинается следующий проход, серии из всех остальных файлов сливаются в этот выходной файл. Процесс сортировки завершается, когда все серии будут объединены в одну серию.
Рассмотрим пример использования трех файлов fl, f2 и f3. Пусть вначале файл fl содержит 13 серий, файл f2 — 8 серий, а f3 — выходной файл. Рассмотрим сам процесс coртировки.

Сначала 8 серий из файлов f 1 и f2 сливаются и посылаются в f3. Файл f2 оказывается свободным, при очередном проходе туда посылаются 5 серий, полученных от слияния записей из f1 и f3, и т.д. до тех пор, пока все серии не сольются в одну в файле f1.

Файлы
                                         f1     f2     f3
Исходное состояние      13     8      0
Первый проход               5      0     8
Второй проход               0      5      3
Третий проход               3      2     0
Четвертый проход         1     0      2
Пятый проход               0     1      1
Шестой проход             1      0      0

Сортировка завершена, отсортированные записи в файле f1.

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

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