Многопутевое слияние

В этом методе исходная лента разделяется не на две, а на m лент (m>2).

Схематично метод простого слияния выглядит так (рис1.):

Рисунок 1 Многопутевое слияние

На рисунке 1- B1,B2, …, Bm соответственно 1,2,.., m –тая дополнительные ленты.

Алгоритм метода работает так: первая серия на ленте А при выполнении фазы разделения помещается на ленту В1, вторая серия-на ленту В2 и т.д., m- тая серия на ленту Вm. M+1 серия на ленту В1, M+2- на ленту В2 и т.д.

После выполнения фазы разделения происходит слияние всех первых серий каждой дополнительной ленты. Для организации слияния в ОП может быть организован массив из m элементов.

После выполнения первой фазы разделения на каждой из дополнительных лент будет размещено примерно ]N/m[ серий. После выполнения второй фазы разделения число серий на каждой ленте ]N/m[ /m.

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