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

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

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

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

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

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

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

1 if 
2    then return
3   
4 
5 
6 

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

1 
2 
3 for  to 
4     do if  або ( і )
5           then 
6                
7           else 
8                
9 for  to 
10    do 

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

Час роботи алгоритму по впорядкуванню елементів задовільняє рекурентному співвідношенню:

, де — час на впорядкування половини масиву, — час на злиття цих половинок.

Враховуючи, що , розв'язком співвідношення є .

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

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

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

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

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