Природне злиття
Очевидно, що кількість читань/перезаписів файлів при використанні цього методу буде не гірше, ніж при застосуванні методу прямого злиття, а в середньому краще. З іншого боку, збільшується кількість порівнянь за рахунок тих, які потрібні для розпізнавання кінців серій. Крім того, оскільки довжина серій може бути довільною, максимальний розмір файлів B і C може бути близький до розміру файлу A.
Збалансоване багатоколійне злиття
В основі методу зовнішнього сортування збалансованим багатоколійним злиттям є розподіл серій вихідного файлу по m допоміжним файлам B1, B2, . Bm та їх злиття в m допоміжних файлів C1, C2, . Cm. На наступному етапі здійснюється злиття файлів C1, C2, . Cm у файли B1, B2, . Bm і т.д., поки B1 або C1 не утворюється одна серія.
Багатоколійне злиття є природним розвитком ідеї звичайного (двоколійного) злиття. Приклад триколійного злиття показаний малюнку 13.3.
Мал. 13.3.
На малюнку 13.4 показаний простий приклад застосування сортування багатоколійним злиттям. Він, звичайно, надто тривіальний, щоб продемонструвати кілька кроків виконання алгоритму, проте достатній як ілюстрація загальної ідеї методу. Зауважимо, що, як показує цей приклад, зі збільшенням довжини серій допоміжні файли з великими номерами (починаючи з номера n) перестають використовуватися, оскільки їм "не дістається" жодної серії. Перевагою сортування збалансованим багатоколійним злиттям є те, що число проходів алгоритму оцінюється як O(log n) (n - число записів у вихідному файлі), де логарифм береться на підставі n. Порядок числа копіювань записів – O(log n). Звичайно, кількість порівнянь не будеменше, ніж при застосуванні методу злиття.
Багатофазне сортування
При використанні розглянутого вище методу збалансованого багатоколійного зовнішнього сортування на кожному кроці приблизно половина допоміжних файлів використовується для введення даних і приблизно стільки ж для виведення серій, що зливаються. Ідея багатофазного сортування полягає в тому, що з наявних m допоміжних файлів (m-1) файл служить для введення послідовностей, що зливаються, а один - для виведення утворених серій. Як тільки один із файлів введення стає порожнім, його починають використовувати для виведення серій, які отримуються при злитті серій нового набору (m-1) файлів. Таким чином, є перший крок, при якому серії вихідного файлу розподіляються по m-1 допоміжному файлу, а потім виконується багатоколійне злиття серій (m-1) файлу, поки в одному з них не утворюється одна серія.
Таблиця 13.2. Приклад початкового розподілу серій, при якому трифазне зовнішнє сортування не призводить до потрібного результату