Time and Space Complexity

Complejidad Temporal:

• O(d * (n + k))
  • donde n es el número de elementos, k es la base (10) y d es el número de dígitos en el valor más grande. Cada una de las d pasadas realiza un trabajo de O(n + k).
• Cuando d es pequeño y fijo, esto se comporta como O(n), más rápido que el O(n log n) de los ordenamientos por comparación.

Complejidad Espacial:

• O(n + k)
  • Cada pasada construye un arreglo de salida de tamaño n y un arreglo de conteo de tamaño k.

Resumen:

• Radix Sort es un ordenamiento estable, no basado en comparaciones, que puede superar a O(n log n) para claves enteras con un número limitado de dígitos.
• Necesita claves que se dividan en dígitos y algo de memoria extra, y esta versión asume enteros no negativos.