635
правок
Изменения
→Introsort
Для предотвращения ухудшения времени работы быстрой сортировки до O(n²) при неудачных входных данных, также можно использовать алгоритм сортировки Introsort.
Он использует быструю сортировку и переключается на пирамидальную сортировку, когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов). Этот подход сочетает в себе достоинства обоих методов с худшим случаем O(n log n) и быстродействием, сравнимым с быстрой сортировкой. Так как оба алгоритма используют сравнения, этот алгоритм также принадлежит классу сортировок на основе сравнений.
==См. также==
