Естествен синтез
Очевидно броят на четенията/пренаписванията на файлове, използващи този метод, няма да бъде по-лош от метода на директно сливане и средно - по-добър. От друга страна, броят на сравненията се увеличава поради тези, необходими за разпознаване на краищата на поредицата. Освен това, тъй като дължината на поредицата може да бъде произволна, максималният размер на файловете B и C може да бъде близък до размера на файл A.
Балансирано сливане с много пътеки
Методът за външно сортиране чрез балансирано обединяване с много пътеки се основава на разпределението на поредицата от изходния файл в m помощни файлове B1, B2,. Bm и ги обединете в m помощни файлове C1, C2,. См. Следващата стъпка е да обедините файлове C1, C2,. Cm към файлове B1, B2,. Bm и др., Докато се образува една серия в B1 или C1.
Многолинейното сливане е естествено развитие на идеята за конвенционално (двупосочно) сливане. Пример за трипосочно сливане е показан на фигура 13.3.
Фигура: 13.3.
Фигура 13.4 показва прост пример за използване на сортиране с обединяване с много пътеки. Разбира се, твърде тривиално е да се демонстрират няколко стъпки от алгоритъма, но е достатъчно, за да се илюстрира общата идея на метода. Имайте предвид, че както показва този пример, с увеличаване на дължината на поредицата, помощните файлове с големи числа (започвайки от номер n) вече не се използват, тъй като те "не получават" нито една поредица. Предимството на балансираното сортиране на многопътечно сливане е, че броят на проходите на алгоритъма се изчислява като O (log n) (n е броят на записите в изходния файл), където логаритъмът се взема в база n. Редът на броя копия на записи е O (log n). Разбира се, броят на сравненията няма да бъде по-малък, отколкото при използването на метода на простото сливане.