63
правки
Изменения
Нет описания правки
# Иначе массив разбивается на две части, которые сортируются рекурсивно.
# После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.
Достоинства:
* устойчивая
Недостатки:
* при любых входных данных время работы {{---}} <tex>O(n\log{n})</tex>
* требуется дополнительно <tex>O(n)</tex> памяти
Проблема с одинаковым временем работы решается в [[Timsort]].
===Слияние двух массивов===
Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2^k=n</tex>, а значит <tex>k=\log n</tex>. Уравнение примет вид <tex>T(n)=nT(1)+ \log n</tex> <tex>O(n)</tex>. Так как <tex>T(1)</tex> {{---}} константа, то <tex>T(n)=O(n)+\log n </tex> <tex>O(n)=O(n\log n)</tex>.
==См. также==
* [[Сортировка кучей]]
