улучшение сложности наихудшего случая быстрой сортировки без преобразования в mergsort

Question

Можно ли изменить сложность быстрой сортировки наихудшего случая с O(n2) на O(nlogn), изменив ее (without converting it to mergsort)?

Answer 1

Обычно наихудшего случая избегают путем переключения на heapsort, если число рекурсий или разбиений разделов становится слишком большим, поскольку heapsort также находится на месте.

https://en.wikipedia.org/wiki/Introsort

Другой способ избежать поведения в худшем случае - использовать медиану медиан, хотя это медленнее.

https://en.wikipedia.org/wiki/Median_of_medians

Как упоминалось в статье, это может быть гибридная быстрая сортировка, которая переключается на медиану медиан, когда уровень рекурсии становится чрезмерным.

https://en.wikipedia.org/wiki/Introselect