Сортування злиттям або об’єднанням

Методи цього класу працюють за таким принципом: невідсортовану вхідну множину довільно розбивають на підмножини М₁,..., М_p. Потім ці підмножини сортують окремо одним з відомих методів сортування і об’єднують в одну відсортовану множину.

Продемонструємо цю схему на двох множинах, оскільки багаторазове злиття можна здійснювати багаторазовим виконанням попарного злиття.

Нехай маємо дві відсортовані множини X і У; потрібно об’єднати їх у множину Z, яка також повинна бути відсортованою. У ролі Z₁ приймаємо min (x₁, y₁) якщо Z₁ = x₁є X, тоді Z₂ = min(x_2, y₁) і т.д.

Для запису алгоритму використовуємо таке позначення: і - індекс для множини X, j - індекс для множини Y, k – індекс для множини Z, i=1..n; j=1..m; k=1..(n+m).

Для зручності розмістимо в кінці кожної множини фіктивні елементи: x_n+1= max, y_m+1 =max.

Алгоритм C

Дано X={ x₁,…, x_n }; Y={ y₁,…, y_m }.

C1. Ініціалізація індексів i=1, j=1, k=1;

C2. Виконувати C3, C4 доки k<n+m.

С3 [Якщо x_i < y_i то [ z_k = x_i; i=i+1 ] інакше [ z_k=y_i, j=j+1 ]

C4. k=k+1 ]

C5. Кінець. Вихід.

В квадратних дужках записані дії які повторюються. Кількість порівнянь, яку необхідно виконати в алгоритмі С для злиття двох множин, дорівнює |x|+|y|=n+m.

Вся процедура злиття разом вимагає не більше ніж n порівнянь для n елементів i потрібно буде виконати log₂ n переходів із однієї множини у другу. Тобтоалгоритм С вимагає п log₂ n порівнянь.

Час роботи алгоритму злиття T (n) для n елементів задовольняє рекурентному співвідношенню: T (n) = 2∙ T (∙ n/2) + O (n), де T (∙ n/2) - час на впорядкування половинимасиву, O (n) - час на злиття цих половинок. Враховуючи, що T (1) = O (1), розв’язком співвідношення є: T (n) = O (n ∙log(n)).