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

Приклад сортування злиттям

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

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

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

Алгоритм сортування

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

Y	…	1	3	…	13	2	4	…	88
	…	m	m + 1		m + s –1	m + s	m + s + 1	…	m + s + r

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

X	…	1	2	3	4	…	13	…	88
	…	m	m + 1	m + 2	m + 3		…		m + s + r

Тепер розглянемо сортування масиву 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	n(n-1)/2	n(1+ë log2nû )	r
10	45	40	1
100	4950	700	7
1000	499500	10000	50
10000	49995000	140000	350

Як бачимо, кожне зростання 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 році його винайшов Джон фон Нейман, один із піонерів програмування.

Псевдокод алгоритму

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

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

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

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

Аналіз алгоритму

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

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

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

Крім того, алгоритм потребує для своєї роботи $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);
}

Алгоритм об'єднання без додаткової пам'яті

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

Псевдокод алгоритму

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

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

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

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

Ідея алгоритму злиття

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

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

1. Знайдемо такі індекси $\;i,j$, що $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 ,$
$j=q\lor A[i]\leq A[j+1],i=c\lor A[c+1]<A[i+1]$
2. Змінимо порядок елементів масиву з $p,p+1,\cdots ,c,c+1,\cdots ,q$ на
$p,p+1,\cdots ,i,c+1,c+2,\cdots ,j,j+1,\cdots ,q,i+1,i+2,\cdots ,c$
3. Викличемо рекурсивне злиття для половин нового масиву.

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

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

Псевдокод алгоритму злиття

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

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

Аналіз алгоритму

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

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

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

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

Застосування

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

Джерела

• Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1

Посилання

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