6.4. Сбалансированное многопутевое слияние
 

Затраты на сортировку последовательностей пропорциональны числу проходов, так как, при каждом проходе пересылаются все данные, в двухфазных сортировках дважды, в однофазных — один раз. Один из способов сократить число пересылок — распределять серии более чем в два файла. Если в исходном файле имеется n серий и они поровну распределяются в N файлов, то первый проход даст n/N серий, второй проход — n/N², третий — n/N³ и т.д. Отсюда общее число проходов, необходимых для сортировки n элементов с помощью N-путевого слияния, равно к = log_Nn, а число пересылок при объединении фаз слияния и разделения в самом худшем случае будет М = nlog_Nn. При каждом проходе будут участвовать N входных и N выходных файлов, в которые по очереди распределяются последовательные серии. Таким образом, получается однофазное многопутевое сбалансированное слияние - разделение.

Алгоритм многопутевого слияния, естественно, сложнее рассмотренных выше. Из N выходных файлов образуется кольцевая очередь. Первоначально n серий данных из исходного файла распределяются поочередно в N выходных файлов, по n/N серий в каждый файл. Первая серия направляется в первый файл, вторая — во второй и т.д., затем по кольцу опять в первый, второй и т.д. до конца исходного файла. Выходные файлы становятся входными, а остальные N файлов образуют кольцевую очередь выходных файлов.

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

Управление слиянием N очередных входных серий в одну выходную серию представляет собой более сложный процесс. Входным файлам присвоим номера i = 1, 2, ..., N. В каждом i-м файле имеется последовательность серий j = 1, 2,…. В процессе слияния текущая j-я серия каждого i-го файла сливается в одну выходную серию. Входной файл может находиться в одном из трех состояний:

1) файл активен, если не исчерпаны записи текущей j-й серии файла;
2) файл временно не активен, если исчерпаны записи текущей j-серии, но не достигнут конец файла. Такой файл не участвует в процессе слияния очередной серии, но активизируется при слиянии следующей серии;
3) файл не активен, если достигнут конец файла, т.е. исчерпаны все серии. В текущем проходе такой файл больше не используется.

Для определения конца текущей серии или конца файла может потребоваться опережающее чтение записи или ведение специальной таблицы.

При формировании очередной выходной серии вначале из каждого активного файла считывается одна запись текущей серии. Среди них выбирается i-я запись с наименьшим ключом и пересылается в активный выходной файл. Активным является тот выходной файл из кольцевой очереди, куда направляются записи формируемой серии. Файл остается активным до конца формирования текущей выходной серии.

Из i-го файла, чья запись была переслана в выходной файл, считывается очередная запись, если только этот входной файл остается активным. Опять выбирается запись с наименьшим ключом и направляется в активный выходной файл. Такой процесс слияния продолжается до исчерпания записей из текущих серий всех N файлов. Затем активизируется очередной выходной файл и начинается процесс формирования следующей выходной серии.

Очередной проход заканчивается, когда будет достигнут конец всех входных файлов. Выходные файлы становятся входными, а входные файлы — выходными, и начинается очередной проход сортировки.

Процесс сортировки заканчивается, когда при очередном проходе будет сформирована одна-единственная серия.