title: Tri faire-valoir
text: # Tri faire-valoir
  
  En informatique, le tri faire-valoir est un algorithme de tri récursif. Il est appelé stooge sort en anglais, nom inspiré des Trois Stooges. Il est présenté en exercice dans le livre Introduction à l'algorithmique de Cormen, Leiserson, Rivest et Stein.
  
  ## Principe
  
  Le principe du tri faire-valoir est le suivant :
  
  * On échange le premier et le dernier élément du tableau à trier s'ils ne sont pas dans le bon ordre.
  * Si le tableau contient plus de trois éléments :
     * on trie le premier 2/3 du tableau ;
     * on trie le dernier 2/3 du tableau ;
     * on retrie le premier 2/3 du tableau à nouveau.
  
  Sa complexité temporelle est $O(n^{log3/log1,5})$ = $O(n^{2,7095...}),$ ainsi cet algorithme est particulièrement inefficace en comparaison avec le tri rapide ou le tri à bulles.
  
  