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

Многоканальную (m-канальную) сортировку слиянием можно выполнить с помо­щью лишь т + 1 файлов (в отличие от описанной выше 2/n-файловой стратегии). При этом выполняется ряд проходов с объединением серий из т файлов в более длинные серии в (т + 1)-м файле. Вот последовательные шаги такой процедуры.

1. В течение одного прохода, когда серии от каждого из т файлов объединяются в серии (т + 1)-го файла, нет нужды использовать все серии от каждого из т входных файлов. Когда какой-либо из файлов становится выходным, он запол­няется сериями определенной длины, причем количество этих серий равно ми­нимальному количеству серий, находящихся в сливаемых файлах.

2. В результате каждого прохода получаются файлы разной длины. Поскольку ка­ждый из файлов, загруженных сериями в результате предшествующих т прохо­дов, вносит свой вклад в серии текущего прохода, длина всех серий на опреде­ленном проходе представляет собой сумму длин серий, созданных за предшест­вующие т проходов. (Если выполнено менее т проходов, можно считать, что гипотетические проходы, выполненные до первого прохода, создавали серии длины 1.)

Подобный процесс сортировки слиянием называется многофазной сортировкой. Точный подсчет требуемого количества проходов как функции от т (количества файлов) и п (количество записей), а также нахождения оптимального начального распределения серий между т файлами оставлен для упражнений. Однако мы при­ведем здесь один пример общего характера.