Motivation

O Counting Sort nunca compara dois elementos. Ele usa seus valores diretamente como índices em um array count, que é o que permite que ele seja executado em tempo linear.

Por que aprender o Counting Sort?

• Tempo linear: ele é executado em O(n + k), onde n é o número de elementos e k é o intervalo de valores. Quando k é pequeno, isso supera O(n log n).
• Estável (quando feito com cuidado): uma base para o Radix Sort, que encadeia várias passagens de counting-sort.
• Uma ideia diferente: ordenar contando os valores em vez de compará-los.

A desvantagem: ele precisa de memória O(k) para o array count, por isso não é adequado quando o intervalo de valores é enorme (por exemplo, ordenar um punhado de números até um bilhão).