Time and Space Complexity

Complexidade de Tempo:

• O(n + k)
  • onde n é o número de elementos e k é o intervalo de valores (max + 1). Uma passagem para contar, uma passagem sobre as contagens para reconstruir.
• Quando k é pequeno e fixo, isso é efetivamente O(n), mais rápido que o O(n log n) de ordenações por comparação.

Complexidade de Espaço:

• O(n + k)
  • O array de contagem usa O(k) e a saída usa O(n).

Resumo:

• Counting Sort é uma ordenação estável, não baseada em comparação, que executa em tempo linear para pequenos intervalos de inteiros.
• É uma escolha ruim quando o intervalo de valores k é muito grande, porque o array de contagem seria enorme. Esta versão assume inteiros não negativos.