Motivation

O Radix Sort nunca compara dois números diretamente. Ele os agrupa por um dígito de cada vez usando uma ordenação auxiliar estável, o que permite quebrar a barreira O(n log n) que as ordenações por comparação não conseguem.

Por que aprender Radix Sort?

• Tempo quase linear: ele é executado em O(d * (n + k)) onde d é o número de dígitos e k é a base (10 aqui). Para números com uma quantidade limitada de dígitos, isso é efetivamente O(n).
• Estável: valores iguais mantêm sua ordem relativa, que é exatamente o que faz com que as passagens dígito a dígito se combinem corretamente.
• Uma ideia diferente: ele mostra que ordenar não precisa significar comparar, um insight importante para chaves inteiras grandes ou de largura fixa.

A compensação: ele precisa de chaves que você possa dividir em dígitos (aqui, inteiros não negativos) e um pouco de memória extra para os buckets.