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

Сортування злиттям (англ. 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

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

Зміст

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

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

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

Можливі оптимізації ред.

Робота алгоритму ред.

Тестування алгоритму ред.

Приклад реалізації на С++ ред.

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

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

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

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

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

Застосування ред.

Джерела ред.

Посилання ред.