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

Матеріал з Вікіпедії — вільної енциклопедії.

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

Алгоритм був винайдений Джоном фон Нейманом у 1945 році.

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

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

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

\;MergeSort(A,p,q)
1 if \; q-p\le\;1
2    then return
3 c \gets\;\lfloor\;(p+q)/2\rfloor\;  
4 \;MergeSort(A,p,c)
5 \;MergeSort(A,c+1,q)
6 \;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\le\;c і \;A[i]\le\;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(n/2)+O(n)\;, де \;T(n/2) — час на впорядкування половини масиву, O(n)\; — час на злиття цих половинок.

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

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

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

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

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

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