Insérer sans @ — fusion optimisée

Chaque @ recopie son membre gauche (chapitre 2) : tri_rapide inf @ ... reparcourt tout le préfixe déjà trié à chaque remontée de la récursion, ajoutant un facteur linéaire. La piste classique est de passer un accumulateur — la liste « déjà triée qui suit » — pour préfixer les éléments par :: (temps constant) au lieu de concaténer :

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

let tri_rapide l = tri_rapide_acc l []

On construit le résultat de droite à gauche par ::, sans aucun @ : la même technique d'accumulateur qu'au renverse du chapitre 2.