Radixsort

Radixsort gehört zur Gruppe der speziellen Sortieralgorithmen. Seine Funktionsweise beruht neben der Endlichkeit der Schlüsselmenge auf der Darstellung der Schlüssel in der Form g(x) = ∑ai*bi mit i=0..d-1, d Anzahl der Ziffern und b die Basis (Radix) der Schlüssel (z.B. 2, 10, ...). a0 ist die am wenigsten signifikante Ziffer.

Da intern Countingsort verwendet wird, kann dieser Algorithmus gleichzeitig zur Gruppe der umhüllenden Sortieralgorithmen gezählt werden.

Bei ganzen Zahlen (Basis 2) oder Strings (Basis 256) ist dieses Verfahren immer zu bevorzugen.

Der Name "Radixsort" kommt von radix (dt. Basis), da das Verfahren auf der Darstellung g(x) der Werte der Elemente beruht. Wobei die Basis während eines Sortiervorganges immer konstant bleibt.
Der Algorithmus wurde zum Sortieren von Lochkarten entwickelt.