Complessità temporale e spaziale

Complessità temporale:

• O(d * (n + k))
  • dove n è il numero di elementi, k è la base (10) e d è il numero di cifre del valore più grande. Ognuno dei d passaggi esegue O(n + k) operazioni.
• Quando d è piccolo e fisso, il comportamento è simile a O(n), più veloce di O(n log n) degli algoritmi di ordinamento per confronto.

Complessità spaziale:

• O(n + k)
  • Ogni passaggio crea un array di output di dimensione n e un array di conteggi di dimensione k.

Riepilogo:

• Radix Sort è un algoritmo di ordinamento stabile e non basato sui confronti, che può superare O(n log n) per chiavi intere con un numero limitato di cifre.
• Richiede chiavi scomponibili in cifre e memoria aggiuntiva; questa versione presuppone interi non negativi.