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

В основе метода внешней сортировки сбалансированным многопутевым слиянием лежит распределение серий исходного файла по m вспомогательным файлам B1, B2,..., Bm и их слияние в m вспомогательных файлов C1, C2,..., Cm. На следующем шаге производится слияние файлов C1, C2,..., Cm в файлы B1, B2,..., Bm и т.д., пока в B1 или C1 не образуется одна серия.

Пример трехпутевого слияния показан на рис. 29.

На рис. 30 показан простой пример применения сортировки многопутевым слиянием. Преимуществом сортировки сбалансированным многопутевым слиянием является то, что число проходов алгоритма оценивается как O(log n) (n - число записей в исходном файле), где логарифм берется по основанию n. Порядок числа копирований записей - O(log n). Число сравнений не будет меньше, чем при применении метода простого слияния.

Рис. 29

Рис. 30