L'idea del radix sort è quello di considerare i numeri come una sequenza di "cifre" e di ordinare i numeri ordinando una cifra per volta. Ti mostro l'idea con un esempio. Supponiamo di voler ordinare i numeri da 0 a 99 ma di non voler usare un array di 100 valori. Consideriamo semplicemente le cifre decimali per comodità in questo caso.
Prendiamo i seguenti valori:
Si inizia considerando la cifra meno significativa (quella delle unità in questo caso) e si passa poi a quelle più significative. Siccome il counting sort usato per l'ordinamento è stabile, cioè preserva l'ordine di elementi con la stessa chiave, alla fine avrai gli elementi ordinati correttamente nel nostro esempio hai i seguenti passaggi (prima riga sequenza di partenza, poi ordinamento in base alle unità e ordinamento in base alle decine):
35 | 2 | 27 | 22 | 97 | 13 | 78 | 50 | 9 |
50 | 2 | 22 | 13 | 35 | 27 | 97 | 78 | 9 |
2 | 9 | 13 | 22 | 27 | 35 | 50 | 78 | 97 |
Nei computer le cifre sono spesso i byte che formano il numero intero (per cui base 256 in un certo senso) ma non è necessario e ho visto implementazioni che usavano invece ad esempio 11 bit. Al contrario del codice che hai scritto di solito non si calcola i limiti effettivi dei dati, ma si usa semplicemente quelli del tipo di dati che si sta usando. Quindi nel caso di interi a 32 bit e l'uso dei byte come cifre ci sono 4 passaggi del counting sort. Nota che questi ordinamenti sono principalmente utili con un grosso numero di valori. Con pochi valori altri algoritmi sono spesso più veloci.