Tri rapide

let rec partition pivot l =
  match l with
  | [] -> ([], [])
  | x :: reste ->
      let (inf, sup) = partition pivot reste in
      if x < pivot then (x :: inf, sup) else (inf, x :: sup)

let rec tri_rapide l =
  match l with
  | [] -> []
  | pivot :: reste ->
      let (inf, sup) = partition pivot reste in
      tri_rapide inf @ [pivot] @ tri_rapide sup

Sur une liste déjà triée, la tête (pivot) est toujours le plus petit : inf est vide et sup contient tout le reste. La récursion ne réduit la taille que de $1$ par étage, d'où $\Theta (n^2)$. Choisir un meilleur pivot (médiane, aléatoire) évite ce travers.