Principe : Elle consiste à placer le premier élément d'un tableau d'éléments à trier (appelé pivot) à sa place définitive en permutant tous les éléments de telle sorte que tous ceux qui lui sont inférieurs soient à sa gauche et que tous ceux qui lui sont supérieurs soient à sa droite. Cette opération s'appelle partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l'opération de partitionnement. Ce processus est répété récursivement, jusqu'à ce que l'ensemble des éléments soient triés.

Algorithme :

tri_rapide(tableau t, entier premier, entier dernier)
    début
      si premier < dernier alors
        pivot <- choix_pivot(t,premier,dernier)
        pivot <- partitionner(t,premier,dernier,pivot)
        tri_rapide(t,premier,pivot-1)
        tri_rapide(t,pivot+1,dernier)
      finsi
    fin

En Caml :

	   let rec qsort = function
   | [] -> []
   | x :: l -> 
     let rec coupelist = function
       | [] -> [], []
       | y :: m -> let a, b = coupelist m in
         if y < x then y :: a, b else a, y :: b
     in let debut, fin = coupelist l
   in (qsort debut) @ [x] @ (qsort fin);;