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

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

Даний алгоритм впорядкування масиву є модифікацією сортування злиттям. Він також є стабільним, але не потребує додаткової пам'яті.

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

Процедура \;StableSort(A,p,q) працює аналогічно процедурі \;MergeSort(A,p,q) сортування злиттям:

\;StableSort(A,p,q)
1 if \; q-p\le\;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).

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

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