Изменения

На практике, когда реализуют алгоритм быстрой сортировки, пытаются улучшить асимптотику в самом плохом случае. Для этого заводится некоторый лимит глубины рекурсии, при превышении которого запускают другую сортировку кучей. Так реализована стандартная сортировка в стандартной библиотеке языка С++. Однако чтобы Часто при превышении порога глубины рекурсии используют сортировку кучей. Замена неё на плавную сортировку могла бы улучшить время работы в на некоторых случаях, можно вместо сортировки кучей использовать плавную сортировкутестах.

Может показаться, что если ограничить глубину рекурсии некоторым числом <tex dpi = 120> D </tex>, независящим от <tex dpi = 120> N </tex>, то быстрая сортировка может начать работать за линейное время. Это ложное утверждениеОчевидно, потому как легко составить пример, на котором сортировка станет работать дольше. Например, пусть сортировке на вход подан массив из что порог глубины рекурсии достигается за <tex dpi =120> 10^9 \cdot D O(N) </tex> элементов. На Казалось бы, что остаточная часть массива должна быть к этому моменту почти упорядочена, а на таком массиве возможна ситуация, когда разделяющий элемент может каждый раз оказываться минимальным или максимальным. Тогда на вход плавная сортировка получит массив из работает за <tex dpi = 120> 10^9 O(N) </tex> элементов. На таком массиве Однако и быстрая, и плавная сортировка в среднем будет являются сортировками на сравнениях. Следовательно по теореме о нижней оценки для сортировки сравнениями такая модификация быстрой сортировки не может работать дольше, быстрее чем быстрая сортировка в силу того<tex dpi = 120> \Omega(N \log{N}) </tex>. Получается, что константа спрятанная в О-натации для неё большетаком случае плавная сортировка будет давать потерю производительности.