Motivazione

Radix Sort non confronta mai direttamente due numeri. Li raggruppa in base a una cifra alla volta usando un ordinamento ausiliario stabile, il che gli permette di superare la barriera O(n log n) che gli ordinamenti basati sui confronti non possono oltrepassare.

Perché imparare Radix Sort?

• Tempo quasi lineare: funziona in O(d * (n + k)), dove d è il numero di cifre e k è la base (10 in questo caso). Per numeri con un numero di cifre limitato, è di fatto O(n).
• Stabile: i valori uguali mantengono il loro ordine relativo, ed è proprio questo che permette ai passaggi cifra per cifra di combinarsi correttamente.
• Un'idea diversa: mostra che ordinare non significa necessariamente confrontare, un'intuizione importante per chiavi intere grandi o a larghezza fissa.

Il compromesso: servono chiavi che si possano scomporre in cifre (qui, interi non negativi) e un po' di memoria aggiuntiva per i contenitori.