How it works?

O Counting Sort funciona em duas fases: contagem e, em seguida, reconstrução.

Processo Passo a Passo:

1. Contagem: crie um array count onde count[v] é a quantidade de vezes que o valor v aparece.
2. Reconstrução: percorra os valores do menor para o maior e escreva cada valor v na saída count[v] vezes.

Exemplo em [4, 2, 2, 8, 3, 3, 1]:

• Conte cada valor: 1 aparece uma vez, 2 duas vezes, 3 duas vezes, 4 uma vez, 8 uma vez.
• Reconstrua em ordem: [1, 2, 2, 3, 3, 4, 8].

Nenhuma comparação foi feita: o próprio valor decidiu para onde cada elemento vai.