Методи цього класу працюють за таким принципом: невідсортовану вхідну множину довільно розбивають на підмножини М1,..., Мp. Потім ці підмножини сортують окремо одним з відомих методів сортування і об’єднують в одну відсортовану множину.
Продемонструємо цю схему на двох множинах, оскільки багаторазове злиття можна здійснювати багаторазовим виконанням попарного злиття.
Нехай маємо дві відсортовані множини X і У; потрібно об’єднати їх у множину Z, яка також повинна бути відсортованою. У ролі Z1 приймаємо min (x1, y1) якщо Z1 = x1є X, тоді Z2 = min(x2, y1) і т.д.
Для запису алгоритму використовуємо таке позначення: і - індекс для множини X, j - індекс для множини Y, k – індекс для множини Z, i=1..n; j=1..m; k=1..(n+m).
Для зручності розмістимо в кінці кожної множини фіктивні елементи: xn+1= max, ym+1 =max.
Алгоритм C
Дано X={ x1,…, xn }; Y={ y1,…, ym }.
C1. Ініціалізація індексів i=1, j=1, k=1;
C2. Виконувати C3, C4 доки k<n+m.
С3 [Якщо xi < yi то [ zk = xi; i=i+1 ] інакше [ zk=yi, j=j+1 ]
C4. k=k+1 ]
C5. Кінець. Вихід.
В квадратних дужках записані дії які повторюються. Кількість порівнянь, яку необхідно виконати в алгоритмі С для злиття двох множин, дорівнює |x|+|y|=n+m.
|
|
Вся процедура злиття разом вимагає не більше ніж n порівнянь для n елементів i потрібно буде виконати log2 n переходів із однієї множини у другу. Тобтоалгоритм С вимагає п log2 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)).