Time and Space Complexity

Complexidade de Tempo:

• O(d * (n + k))
  • onde n é o número de elementos, k é a base (10) e d é o número de dígitos no maior valor. Cada uma das d passagens realiza O(n + k) de trabalho.
• Quando d é pequeno e fixo, isso se comporta como O(n), mais rápido que o O(n log n) de ordenações por comparação.

Complexidade de Espaço:

• O(n + k)
  • Cada passagem constrói um array de saída de tamanho n e um array de contagem de tamanho k.

Resumo:

• O Radix Sort é uma ordenação estável, não baseada em comparação, que pode superar O(n log n) para chaves inteiras com um número limitado de dígitos.
• Ele precisa de chaves que se dividam em dígitos e de memória extra, e esta versão assume inteiros não negativos.