Introsort

Introspective sort : tri introspectif.

Besoin

Pallier le pire des cas du tri rapide.

Analyse

Démarre avec un tri rapide puis utilise un tri par tas lorsque la profondeur de récursivité dépasse une certaine limite prédéfinie. Ainsi, sa complexité dans le pire cas devient O(n log n).