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

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

Джерела

Дональд Кнут. 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.

Посилання

п о р Алгоритми сортування
Теорія	Обчислювальна складність \| Нотація великого О \| Відношення порядку \| Список \| Стабільність \| Сортування порівняннями \| Квантове сортування
Сортування обміном	Сортування бульбашкою \| Сортування змішуванням \| Odd-even sort \| Сортування гребінцем \| Сортування гнома \| Швидке сортування
Сортування вибором	Сортування вибором \| Пірамідальне сортування
Сортування включенням	Сортування включенням \| Сортування Шелла \| Сортування бінарним деревом \| Сортування вставкою з проміжками \| Patience sorting^[en]
Сортування злиттям	Сортування злиттям \| Ниткоподібне сортування
Алгоритми без порівнянь	Сортування за розрядами \| Сортування комірками \| Сортування підрахунком \| Цифрове сортування \| Burstsort^[en] \| Bead sort^[en]
Інші	Топологічне сортування \| Sorting network^[en] \| Bitonic sorter^[en]
Непрактичні алгоритми	Випадкове сортування \| Stooge sort

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

Статус версії сторінки

Зміст

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

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

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

Можливі оптимізації

Робота алгоритму

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

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

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

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

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

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

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

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

Джерела

Посилання

Навігаційне меню

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

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

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

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

Можливі оптимізації

Робота алгоритму

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

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

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

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

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

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

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

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

Джерела

Посилання

Навігаційне меню

Пошук