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

Кучер В.Г.

Просте злиття

При простому злитті довжина серії фіксується.

Так, у вихідному несортированном файлі всі серії складаються з одного елемента. Після першого кроку розмір збільшується до двох. Далі – 4, 8, 16 і так далі.

Працює це наступним чином:

  • Вихідний файл (f) ділиться на два допоміжних – f1, f2.
  • Вони знову зливаються в один файл (f), але при цьому всі елементи попарно порівнюються і утворюють вже пари. Розмір серії на цьому етапі стає дорівнює двом.
  • Повторюється крок 1.
  • Повторюється крок 2, але при цьому зливаються вже впорядковані двійки, утворюючи відсортовані четвірки.
  • Цикл продовжується, супроводжуючись збільшенням серії на кожному витку, до тих пір, поки весь файл не буде відсортовано.
    • Цікаве:  Заглянемо в майбутнє: що буде в 3000 році, якими стануть люди?

    Як зрозуміти, що зовнішня сортування простим злиттям завершена?

    • нова довжина серії (після злиття) не менше загальної кількості елементів;
    • залишилася всього одна серія;
    • допоміжний файл f2 залишився порожнім.

    Недоліки простого злиття наступні: так як довжина серій фіксована на кожному проході злиття, частково впорядковані дані будуть оброблятися так само довго, як і абсолютно хаотичні.

    Сторінка: 1 2 3 4 5 6 7 8 9 10