IntroSort
Во многих языках программирования часто используется сортировка, называемая IntroSort, которая представляет собой модификацию быстрой сортировки(qsort). эта модификация гарантирует время работы не более O(nlog(n)) на любых данных и при этом в среднем работает как qsort(то есть быстрее, чем , например, heap sort).
Принципы работы алгоритма intro sort:
- Если количество элементов крайне мало (n<7), то производится разбор случаев с помощью операций ветвления и обменов, делающих минимальное количество действий
- В другом случае запускается qsort
- Если очередной вызов qsort работает на слишком большой глубине, то на этом уровне массива запускается heapsort