Le tri par dénombrement

let tri_denombrement t k =
  let compte = Array.make (k + 1) 0 in
  for i = 0 to Array.length t - 1 do
    compte.(t.(i)) <- compte.(t.(i)) + 1
  done;
  let resultat = Array.make (Array.length t) 0 in
  let pos = ref 0 in
  for v = 0 to k do
    for _j = 1 to compte.(v) do
      resultat.(!pos) <- v;
      pos := !pos + 1
    done
  done;
  resultat

On compte les occurrences de chaque valeur (compte.(v)), puis on réécrit chaque valeur v autant de fois qu'elle apparaît, dans l'ordre croissant. Aucune comparaison : on exploite que les valeurs sont des indices possibles. C'est plus rapide que $\Theta (n\log n)$, mais au prix d'une hypothèse forte (entiers bornés) et d'un tableau auxiliaire de taille $k+1$.