Сортування злиттям

Сортування злиттям (англ. merge sort) — алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй».

В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової.

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

Нехай у масиві Y з елемента Y[m] починається впорядкована ділянка довжиною s, а з елемента Y[m + s] – впорядкована ділянка довжини r. Наприклад,

Результатом злиття повинна бути ділянка довжини r + s у масиві X:

Тепер розглянемо сортування масиву A злиттям. На першому кроці елементи A[1], …, A[n] копіюються в допоміжний масив B[1], …, B[n]. Його елементи розглядаються парами B[1] і B[2], B[3] і B[4] тощо як упорядковані послідовності довжиною lp = 1 і зливаються за допомогою процедури mrg в масив A. Тепер там є впорядковані ділянки довжиною 2. За непарного n останній елемент A[n] залишається без змін як послідовність довжиною 1.

На наступному кроці після копіювання в масив B зливаються пари упорядкованих ділянок B[1]B[2] і B[3]B[4], B[5]B[6] і B[7]B[8] тощо. З'являються впорядковані ділянки довжиною 4. Нехай t = nmod4 — довжина залишку масиву після останньої повної четвірки елементів. При t = 1 або t = 2 останні t елементів утворюють упорядковану ділянку після попереднього кроку. При t = 3 зливаються упорядкована пара B[n – 1]B[n – 2] та ділянка B[n] у ділянку довжиною t.

Кроки повторюються з подвоєнням довжин упорядкованих ділянок lp, поки lp < n.

Розглянемо сортування злиттям масиву <11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1> довжини n = 11. Упорядковані послідовності в ньому вказуються в дужках <>, а пари таких, що зливаються, відокремлені ";": < <11><10>; <9><8>; <7><6>; <5><4>; <3><2>; <1> >, lp = 1 < <10, 11><8, 9>; <6, 7><4, 5>; <2, 3><1> >, lp = 2 < <8, 9, 10, 11><4, 5, 6, 7>;<1, 2, 3> >, lp=4 < <4, 5, 6, 7, 8, 9, 10, 11><1, 2, 3> >, lp = 8 <1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11>, lp = 16, lp³ n.

Як бачимо, нам знадобилося 4 кроки злиття для того, щоб одержати впорядкований масив. Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp = 2k. Якщо 2k = n, то масив упорядковано. Якщо 2k > n, але 2k – 1 < n, то при виконанні останнього кроку мають місце співвідношення lp = 2k – 1 = 2k / 2 > n/2, npp = 0, tl = n > lp, і злиття ділянки довжиною lp та залишку довжиною n – lp дає впорядкований масив.

Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2k < 2n, тобто k < 1 + log n, і це означає, що тіло циклу while виконується 1 + log2n =O(log n) разів. Отже, складність алгоритму оцінюється як O(n log n).

Запишімо в таблицю значення виразів n, n(n – 1)/2, n(1+ë log2nû ) та округлене відношення r двох останніх:

Як бачимо, кожне зростання n у 10 разів веде до зростання n(n-1)/2 та n(1+ë log2nû ) приблизно в 100 й 14 разів відповідно, і за n=10000 сортування злиттям виконується в сотні разів скоріше, ніж бульбашкове! Зауважимо, що в наведеному алгоритмі сортування злиттям копіювання масиву в допоміжний указано лише для того, щоб ідею алгоритму було простіше сприйняти. Цей алгоритм нескладно переробити так, щоб замість копіювання в додатковий масив відбувалося злиття в нього упорядкованих ділянок. Отже, на кроках з номерами 1, 3, 5, … має відбуватися злиття в допоміжний масив, а на кроках 2, 4, 6, … – злиття в протилежному напрямку. Переробка алгоритму залишається вправою. Сортування злиттям можна задати рекурсивно: масив поділяється на дві приблизно рівні частини, які після сортування (тим самим способом – ось рекурсія!) зливаються. Коли ж довжина частини масиву зменшується до 1, відбувається просто повернення з рекурсії. Цей алгоритм уточнюється наступною процедурою Mrgrec. На відміну від процедури Merges, вона має два параметри-масиви (той, що сортується, та допоміжний), а також два числові параметри (початок і кінець частини масиву, яка сортується). Крім того, спочатку відбувається злиття ділянок основного масиву в допоміжний, а потім копіювання в основний: Ця функція набагато коротше нерекурсивної функції, але виконання її довше. Власне сортування починається лише після повернення з викликів, у яких l=r, а це практично "середина дистанції". Завершуючи описання сортування злиттям, скажемо, що цей алгоритм є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман, один із піонерів програмування.

Процедура ${\displaystyle \;MergeSort(A,p,q)}$ здійснює часткове впорядкування масиву ${\displaystyle \;A}$, впорядковуючи його елементи з p-го по q-й ${\displaystyle (\;MergeSort(A,1,length(A))}$ здійснить впорядкування всього масиву).

${\displaystyle \;MergeSort(A,p,q)}$
1 if ${\displaystyle \;q-p<1}$
2    then return
3 ${\displaystyle c\gets \;\lfloor \;(p+q)/2\rfloor \;}$  
4 if ${\displaystyle \;q-p>1}$
5    ${\displaystyle \;MergeSort(A,p,c)}$
6    ${\displaystyle \;MergeSort(A,c+1,q)}$
7 ${\displaystyle \;Merge(A,p,c,q)}$

${\displaystyle \;MergeSort}$ використовує допоміжну процедуру ${\displaystyle \;Merge(A,p,c,q)}$, що здійснює об'єднання частин масиву A з p-го по c-й елемент і з c+1-го по q-й елемент в один впорядкований підмасив. Для цього використовується один додатковий масив ${\displaystyle \;B}$ такої ж довжини як і ${\displaystyle \;A}$ (В деяких реалізаціях ${\displaystyle B\;}$ вдвічі коротший за ${\displaystyle A\;}$ — мінімально можлива його довжина).

${\displaystyle Merge(A,p,c,q)\;}$
1 ${\displaystyle i\gets \;p}$
2 ${\displaystyle j\gets \;c+1}$
3 for ${\displaystyle k\gets \;p}$ to ${\displaystyle q\;}$
4     do if ${\displaystyle \;j>q}$ або (${\displaystyle \;i\leq \;c}$ і ${\displaystyle \;A[i]\leq \;A[j]}$)
5           then ${\displaystyle B[k]\gets \;A[i]}$
6                ${\displaystyle i\gets \;i+1}$
7           else ${\displaystyle B[k]\gets \;A[j]}$
8                ${\displaystyle j\gets \;j+1}$
9 for ${\displaystyle k\gets \;p}$ to ${\displaystyle q\;}$
10    do ${\displaystyle \;A[k]=B[k]}$

Час роботи алгоритму ${\displaystyle T(n)\;}$ по впорядкуванню ${\displaystyle \;n}$ елементів задовільняє рекурентному співвідношенню:

${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)\;}$, де ${\displaystyle \;T\left({\frac {n}{2}}\right)}$ — час на впорядкування половини масиву, ${\displaystyle O(n)\;}$ — час на злиття цих половинок.

Враховуючи, що ${\displaystyle \;T(1)=O(1)}$, розв'язком співвідношення є ${\displaystyle \;T(n)=O(n\log \;n)}$.

Крім того, алгоритм потребує для своєї роботи ${\displaystyle O(n)\;}$ додаткової пам'яті.

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

Швидкість алгоритму є асимптотично оптимальною. Але її можна пришвидшити в константну кількість разів.

• Оптимізація впорядкування невеликих частин масиву — невеликі частини масиву (наприклад, при q-p<50) впорядковувати сортуванням вставкою.
• Оптимізація кількості копіювань елементів — при злитті двох впорядкованих масивів в один, кожен елемент копіюється двічі (спочатку у тимчасовий масив, а потім знову у початковий). Кількість копіювань можна зменшити удвічі, якщо по черзі використовувати для об'єднання початковий і тимчасовий масиви. Тоді можна не виконувати зайві операції копіювання (рядки 9-10 процедури Merge).

Схема алгоритму для конкретного прикладу послідовності

Проілюструємо алгоритм сортування на такій послідовності: 42 5 30 36 25 10 37 49 0 0

На початку сортування відсортовані підпослідовності містять в собі по одному елементу.

Крок 1: 5 42 | 30 36 | 10 25 | 37 49 | 0 0

Крок 2: 5 30 36 42 | 10 25 37 49 | 0 0

Крок 3: 5 10 25 30 36 37 42 49 | 0 0

Крок 4: 0 0 5 10 25 30 36 37 42 49

Для перевірки правильності сортування звіримо сортування проведене програмою з сортуванням за даним алгоритмом вручну.

Проведемо сортування наступної послідовності: 56 19 3 95 23 17 38 44 69 73 84

На початку сортування послідовність є розбита на відсортовані підпослідовності по одному елементу в кожній.

56 | 19 | 3 | 95 | 23 | 17 | 38 | 44 | 69 | 73 | 84

далі кожні дві підпослідовності зливаються в одну відсортовану підпослідовність: 19 56 | 3 95 | 17 23 | 38 44 | 69 73 | 84

на наступному кроці отримаємо наступний результат злиття: 3 19 56 95 | 17 23 38 44 | 69 73 84 |

потім: 3 17 19 23 38 44 56 95 | 69 73 84 |

на останньому кроці отримаємо відсортовану послідовність: 3 17 19 23 38 44 56 69 73 84 | 95

Послідовність була відсортована за 4 кроки.

#include <algorithm>
#include <vector>
using namespace std;

template <typename T>
void merge_sort(T* elems, //original array
                T* tmp_elems, //temp array to hold intermediate results, should be same size as array "elems"
                size_t size)
{
    if (size <= 1) {return;} //nothing to sort
    
    const size_t left_size = size / 2;
    const size_t right_size = size - left_size;
    
    merge_sort(elems, tmp_elems, left_size);
    merge_sort(elems + left_size, tmp_elems + left_size, right_size);
    
    T* leftIt = elems; // pointer to walk through left part
    T* const pivot = elems + left_size; //end of left part, start of right  part
    T* rightIt = pivot; // pointer to walk through right part
    T*const end = elems + size;
    T* outputIt = tmp_elems; //pointer to where to write when merging left and right subparts
    
    while (true)
    {
        if (*leftIt < *rightIt)
        {
            *outputIt++ = *leftIt++;
            if (leftIt == pivot)
            {
                // copy the rest of right part that has not been copied yet
                copy(rightIt,
                     end,
                     outputIt);
                break;
            }
        }
        else
        {
            *outputIt++ = *rightIt++;
            if (rightIt == end)
            {
                // copy the rest of left part that has not been copied yet
                copy(leftIt,
                     pivot,
                     outputIt);
                break;
            }
        }
    }
    
    copy(tmp_elems,
         tmp_elems + size,
         elems);
}

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

Процедура ${\displaystyle \;StableSort(A,p,q)}$ працює аналогічно процедурі ${\displaystyle \;MergeSort(A,p,q)}$ сортування злиттям:

${\displaystyle \;StableSort(A,p,q)}$
1 if ${\displaystyle \;q-p\leq \;1}$
2    then return
3 ${\displaystyle c\gets \;\lfloor \;(p+q)/2\rfloor \;}$  
4 ${\displaystyle \;StableSort(A,p,c)}$
5 ${\displaystyle \;StableSort(A,c+1,q)}$
6 ${\displaystyle \;ModifiedMerge(A,p,c,q)}$

Відмінність алгоритмів полягає в процедурі ${\displaystyle \;ModifiedMerge}$, яка здійснює об'єднання двох впорядкованих масивів без додаткової пам'яті, але за час ${\displaystyle \;O(n\log \;n)}$.

Існує декілька алгоритмів об'єднання двох впорядкованих масивів, що не потребують додаткової пам'яті. Розглянемо лише один з них.

Нехай алгоритм має об'єднати дві частини масиву ${\displaystyle A}$ — з ${\displaystyle p}$-го по ${\displaystyle c}$-й і з ${\displaystyle c+1}$-го по ${\displaystyle q}$-й.

Виконаємо об'єднання в декілька етапів:

1. Знайдемо такі індекси ${\displaystyle \;i,j}$, що ${\displaystyle p\leq i\leq c,c+1\leq j\leq q,(i-p+1+j-c)=\left\lfloor {\frac {q-p+1}{2}}\right\rfloor ,}$
${\displaystyle j=q\lor A[i]\leq A[j+1],i=c\lor A[c+1]<A[i+1]}$
2. Змінимо порядок елементів масиву з ${\displaystyle p,p+1,\cdots ,c,c+1,\cdots ,q}$ на
${\displaystyle p,p+1,\cdots ,i,c+1,c+2,\cdots ,j,j+1,\cdots ,q,i+1,i+2,\cdots ,c}$
3. Викличемо рекурсивне злиття для половин нового масиву.

Тобто, спочатку ми знаходимо елементи, що мають лежати в першій половині масиву (найменші), потім переміщаємо найменші елементи в цю половину. Тоді можна окремо впорядкувати першу і другу половини масиву (кожна з половин також буде складатися з двох впорядкованих частин, що треба об'єднати).

Пункт 1, можна виконати за один лінійний прохід. Другий крок — це по-суті циклічний зсув частини масиву на j елементів. Він може бути виконаний за лінійний час, наприклад, за допомогою трьох перегортань.

${\displaystyle \;ModifiedMerge(A,p,c,q)}$
1. if ${\displaystyle p>c\;}$ або ${\displaystyle \;c+1>q}$
2.    then return
3. ${\displaystyle N\leftarrow q-p+1}$
4. ${\displaystyle m\leftarrow 0}$
5. ${\displaystyle i\leftarrow p-1}$
6. ${\displaystyle j\leftarrow c}$
7. While ${\displaystyle m<\left\lfloor {\frac {N}{2}}\right\rfloor }$ 
8. do    if ${\displaystyle j=q\lor (i<c\land A[i+1]<A[j+1])}$
9.       then ${\displaystyle i\leftarrow i+1}$
10.      else ${\displaystyle j\leftarrow j+1}$
11.      ${\displaystyle m\leftarrow m+1}$
12. ${\displaystyle \;Reverse(A,i+1,c+1)}$
13. ${\displaystyle \;Reverse(A,c+1,q)}$
14. ${\displaystyle \;Reverse(A,i+1,q)}$
15. ${\displaystyle \;ModifiedMerge(A,p,i,j-c+i)}$
16. ${\displaystyle \;ModifiedMerge(A,j-c+i+1,q-c+i+1,q)}$

Функція ${\displaystyle \;Reverse(A,a,b)}$ перегортає або дзеркально відображає частину масиву A з a-го по b-й елементи включно.

Спочатку проаналізуймо функцію ModifiedMerge. Вона виконує два кроки, що потребують O(n) часу, і двічі викликає себе від масиву, що у двічі менший за початковий.

Отже, час роботи функції на масиви довжиною n: ${\displaystyle T(n)=O(n)+2T\left({\frac {n}{2}}\right)=O(n\log n)}$

Тепер можемо визначити час роботи алгоритму впорядкування, він виражається рівнянням:

${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(n\log n)=O(n\log ^{2}n)}$

Алгоритм використовується в деяких реалізаціях функції stable_sort() з стандартної бібліотеки шаблонів (STL) мови програмування C++.

• Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — ISBN 0-201-89685-0.(англ.)
• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. II. Сортування і порядкові статистики. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
• Креневич А. П. Алгоритми і структури даних. — Київ : ВПЦ "Київський Університет", 2021. — 200 с.

• Алгоритм
• Наочна демонстрація сортування злиттям національним танцювальним ансамблем трансильванських німців на YouTube