title: Introsort
text: # 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)
  