Come funziona?

Radix Sort elabora una posizione delle cifre alla volta, dalla meno significativa (unità) alla più significativa. Ogni passaggio utilizza un ordinamento stabile, così il lavoro svolto nei passaggi precedenti viene preservato.

Procedimento passo dopo passo:

1. Ordina in base alla cifra delle unità utilizzando un ordinamento per conteggio stabile.
2. Ordina in base alla cifra delle decine, mantenendo l'ordine precedente in caso di parità.
3. Continua con le centinaia, le migliaia e così via, finché non hai elaborato la posizione della cifra del numero più grande.

Esempio su [170, 45, 75, 90, 2, 802, 24, 66]:

• Per cifra delle unità: [170, 90, 2, 802, 24, 45, 75, 66]
• Per cifra delle decine: [2, 802, 24, 45, 66, 170, 75, 90]
• Per cifra delle centinaia: [2, 24, 45, 66, 75, 90, 170, 802]

Dopo l'ultima cifra, l'array è completamente ordinato. La magia sta nel fatto che la stabilità mantiene intatto l'ordine delle cifre meno significative mentre subentrano quelle più significative.