Radix sort

Questa voce o sezione sull'argomento informatica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

Radix sort
Esempio di funzionamento dell'algoritmo.
Classe	Algoritmo di ordinamento
Struttura dati	Array
Caso peggiore temporalmente	${\displaystyle O(kN)}$
Caso peggiore spazialmente	${\displaystyle O(kN)}$
Ottimale	Dipende dai dati
Manuale

Il radix sort è un algoritmo di ordinamento per valori numerici interi con complessità computazionale O(${\displaystyle nk}$), dove ${\displaystyle n}$ è la lunghezza dell'array e ${\displaystyle k}$ è la media del numero di cifre degli ${\displaystyle n}$ numeri.

Radix sort utilizza un procedimento controintuitivo per l'uomo, ma più facilmente implementabile. Esegue gli ordinamenti per posizione della cifra ma partendo dalla cifra meno significativa. Questo affinché l'algoritmo non si trovi a dovere operare ricorsivamente su sottoproblemi di dimensione non valutabili a priori.