Time and Space Complexity

Complexité temporelle :

• O(n + k)
  • où n est le nombre d'éléments et k est la plage de valeurs (max + 1). Une passe pour compter, une passe sur les comptes pour reconstruire.
• Lorsque k est petit et fixe, c'est effectivement O(n), plus rapide que le O(n log n) des tris par comparaison.

Complexité spatiale :

• O(n + k)
  • Le tableau de comptage utilise O(k) et la sortie utilise O(n).

Résumé :

• Le tri par comptage (Counting Sort) est un tri stable, sans comparaison, qui s'exécute en temps linéaire pour de petites plages d'entiers.
• Il est peu adapté lorsque la plage de valeurs k est très grande, car le tableau de comptage serait immense. Cette version suppose des entiers non négatifs.