==Сложность==
Во время построения последовательности куч <tex dpi = 120> O(N) </tex> раз выполняется вставка элемента. И потом ещё <tex dpi = 120> O(N) </tex> раз выполняется удаление элемента при процедуре получения отсортированного массива. Таким образом сложность плавной сортировки составляет <tex dpi = 120> O(N\log{N}) </tex>.
Однако если подать на вход плавной сортировке уже отсортированный массив===Построение последовательности===Получение последовательности куч, для которых не выполняется инвариант, асимптотика будет составлять очевидно производится за <tex dpi = 120> O(N) </tex>. Дело По указанному выше утверждению <tex dpi = 120> N </tex> можно представить в томвиде суммы длин куч. Пусть <tex dpi = 120> N = L(k_1) + L(k_2) + ... + L(k_n) </tex>, что во время процедуры получения последовательности тогда выполнение операции '''heapify''' для всех куч мы всегда будем вставлять элемент, который больше остальных уже находящихся в выполнится за <tex dpi = 120> O(L(k_1)) + O(L(k_2)) + ... + O(L(k_n)) = O(N) </tex>. В итоге построение последовательностивыполняется за <tex dpi = 120> O(N) + O(N) + O(\log^2{N}) = O(N) </tex>. Поэтому восстановление свойства ===Получение отсортированного массива===Так как <tex dpi = 120> O(N) </tex> выполняется удаление максимального элемента из последовательности будет выполняться , то вся эта операция выполняется за <tex dpi = 120> O(1N\log{N}) </tex> . Следовательно, сортировка в худшем случае выполняется за <tex dpi = 120> O(так как алгоритм только посмотрит N\log{N}) </tex>. Однако если подать на корень соседней кучивход плавной сортировке уже отсортированный массив, а просеивание закончится сразу потому что новый элемент асимптотика будет больше своих детейсоставлять <tex dpi = 120> O(N)</tex>. Операция Дело в том, что операция получения и удаления максимального элемента будет тоже выполняться за <tex dpi = 120> O(1) </tex>, потому что в силу построения в корнях куч-детей будут новые максимальные элементы и следовательно восстановление свойства последовательности закончится на просмотре корня соседней кучи. В итоге, так как алгоритм <tex dpi =120> O(N) </tex> раз вставляет, а потом и удаляет элементы, получается асимптотика <tex dpi = 120> O(N) </tex>.
===Достоинства===
На практике, когда реализуют алгоритм быстрой сортировки, пытаются улучшить асимптотику в самом плохом случае. Для этого заводится некоторый лимит глубины рекурсии, при превышении которого запускают сортировку кучей. Так реализована стандартная сортировка в стандартной библиотеке языка С++. Однако чтобы улучшить время работы в некоторых случаях, можно вместо сортировки кучей использовать плавную сортировку.
Использование плавной сортировки вместо сортировки кучей не улучшит итоговую асимптотикуМожет показаться, однако что если ограничить глубину рекурсии некоторым числом <tex dpi = 120> D </tex>, независящим от <tex dpi = 120> N </tex>, то быстрая сортировка может начать работать за счет тоголинейное время. Это ложное утверждение, потому как легко составить пример, на котором сортировка станет работать дольше. Например, пусть сортировке на вход подан массив из <tex dpi =120> 10^9 \cdot D </tex> элементов. На таком массиве возможна ситуация, что в некоторых случаях асимптотика smoothsort стремится к когда разделяющий элемент может каждый раз оказываться минимальным или максимальным. Тогда на вход плавная сортировка получит массив из <tex dpi = 120> O(N) 10^9 </tex> должна уменьшится элементов. На таком массиве плавная сортировка в среднем будет работать дольше, чем быстрая сортировка в силу того, что константа. Изспрятанная в О-за этого время работы должно уменьшитьсянатации для неё больше.
==См. также==
