Time and Space Complexity

Complexité temporelle :

• O(d * (n + k))
  • où n est le nombre d'éléments, k est la base (10) et d est le nombre de chiffres de la plus grande valeur. Chacune des d passes effectue un travail en O(n + k).
• Lorsque d est petit et fixe, cela se comporte comme O(n), ce qui est plus rapide que le O(n log n) des tris par comparaison.

Complexité spatiale :

• O(n + k)
  • Chaque passe construit un tableau de sortie de taille n et un tableau de comptage de taille k.

Résumé :

• Le tri radix (Radix Sort) est un tri stable, sans comparaison, qui peut surpasser O(n log n) pour des clés entières avec un nombre limité de chiffres.
• Il nécessite des clés qui se divisent en chiffres et de la mémoire supplémentaire, et cette version suppose des entiers non négatifs.