Introsort
# Introsort

Introsort ou introspective sort est un algorithme de tri par comparaisons. C'est une variante du tri rapide inventée par David Musser en 1997. Par rapport au tri rapide, Introsort a l'avantage d'avoir une complexité $O(n\log n)$ dans le pire cas.

## Principe

L'algorithme de tri rapide est ralenti lorsque le pivot choisi se retrouve souvent au début ou à la fin du sous-tableau trié. Dans ce cas, la profondeur de récursion est en $O(n)$ et le temps total en $O(n^{2})$, ce qui est un temps comparable à un tri par sélection. Mais en moyenne, le tri rapide est efficace : sa complexité est $O(n\log n)$.

Introsort, pour pallier cet inconvénient, utilise un compteur de récursion. Ainsi il mesure au fur et à mesure la profondeur de récursion en cours (d'où le nom de l'algorithme). Quand la profondeur dépasse $K\log n$ où K est une constante, on trie le sous-tableau restant avec un algorithme dont la complexité est $O(n\log n)$ dans tous les cas, par exemple un tri par tas ou un Smoothsort.

Tout comme le tri rapide, Introsort peut être optimisé en triant les sous-listes de moins de 15 éléments avec un tri par insertion ou un tri de Shell, au fur et à mesure, ou à la fin (principe de Sedgesort).

## Algorithme

Avec A: Tableau et n = Longueur(A)

Faire Introsort(A, 2*PartieEntière(Log2(n)) )

* Procédure Introsort (A : Tableau[Min..Max], ProfondeurLimite : Entier > 0)
   * Initialiser
      * CurMin := Min et CurMax := Max
      * Pivot := A[PartieEntière((Min + Max) / 2)]
   * Répéter jusqu'à ce que CurMin > CurMax
      * Tant que A[CurMin] < Pivot, CurMin := CurMin + 1
      * Tant que A[CurMax] > Pivot, CurMax := CurMax - 1
      * Si CurMin < CurMax alors Echanger(A[CurMin], A[CurMax])
      * CurMin = CurMin + 1
      * CurMax = CurMax - 1
   * Si CurMax > Min
      * Si ProfondeurLimite = 1 alors faire Heapsort(A[Min..CurMax])
      * Sinon faire Introsort(A[Min..CurMax], ProfondeurLimite - 1)
   * Si CurMin < Max
      * Si ProfondeurLimite = 1 alors faire Heapsort(A[CurMin..Max])
      * Sinon faire Introsort(A[CurMin..Max], ProfondeurLimite - 1)
