Сортування злиттям модифіковане

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

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

Процедура ${\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 с. — .(англ.)
• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. II. Сортування і порядкові статистики. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .

Посилання

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