Изменения

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