Tri faire-valoir
# 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.

