Come funziona?

Counting Sort funziona in due fasi: conteggio, poi ricostruzione.

Procedura passo passo:

1. Conteggio: crea un array count in cui count[v] indica quante volte compare il valore v.
2. Ricostruzione: scorri i valori dal più piccolo al più grande e scrivi ogni valore v nell'output count[v] volte.

Esempio su [4, 2, 2, 8, 3, 3, 1]:

• Conta ogni valore: 1 compare una volta, 2 due volte, 3 due volte, 4 una volta, 8 una volta.
• Ricostruisci in ordine: [1, 2, 2, 3, 3, 4, 8].

Non sono stati effettuati confronti: è stato il valore stesso a determinare dove va ogni elemento.