Збалансоване багатошляхове злиття

В основі методу зовнішнього сортування збалансованим багатошляховим злиттям є розподіл серій початкового файлу по m допоміжних файлів В1, В2, …, Вm і їх злиття в m допоміжних файлів С1, С2, …, Сm. На наступному кроці здійснюється злиття файлів С1, С2, …, Сm у файли В1, В2, …, Вm і т.ін., поки в В1 або С1 не утворюється одна серія.

Багатошляхове злиття є природним розвитком ідеї звичного (двошляхового) злиття, ілюстрованого а рисунку 35. Приклад тришляхового злиття показан на рисунку 36.

На рисунку 37 показаний простий приклад застосування сортування багатошляховим (багатофазним) злиттям.

Рисунок 36 – а) Тришляхове злиття. Початок.

Рисунок 36 – б) Тришляхове злиття. Закінчення.

Рисунок 37 – Багатофазне злиття.

Він, зазвичай, дуже тривіальний, щоб продемонструвати декілька кроків виконання алгоритму, проте достатній як ілюстрація загальної ідеї методу. Як показує цей приклад, у міру збільшення довжини серій допоміжні файли з великими номерами (починаючи з номера n) перестають використовуватися, оскільки їм ≪не дістається≫ жодної серії. Перевагою сортування збалансованим багатофазним злиттям є те, що кількість проходжень алгоритму оцінюється як Θ (log n) (n – кількість записів у початковому файлі), де логарифм береться по n. Порядок кількості копіювань записів - (log n). Зазвичай, кількість порівнянь не буде меншою, ніж при застосуванні методу простого злиття.