Motivation

Radix Sort nunca compara dos números directamente. Los agrupa por un dígito a la vez utilizando un ordenamiento auxiliar estable, lo que le permite romper la barrera de O(n log n) que los ordenamientos por comparación no pueden superar.

¿Por qué aprender Radix Sort?

• Tiempo casi lineal: se ejecuta en O(d * (n + k)) donde d es el número de dígitos y k es la base (10 aquí). Para números con una cantidad limitada de dígitos, eso es efectivamente O(n).
• Estable: los valores iguales mantienen su orden relativo, que es exactamente lo que hace que las pasadas dígito por dígito se combinen correctamente.
• Una idea diferente: muestra que ordenar no tiene por qué significar comparar, una perspectiva importante para claves de enteros grandes o de ancho fijo.

La contrapartida: necesita claves que se puedan dividir en dígitos (aquí, enteros no negativos) y algo de memoria extra para los buckets.