Radixsort

Radixsort (von lateinisch radix ‚Wurzel‘, ‚Basis‘) oder auch Distributionsort (von englisch distribution ‚Verteilung‘), oder im Deutschen Fachverteilen, ist ein lineares Sortierverfahren, das auf Countingsort oder Bucketsort basiert. Das Sortierverfahren hat, unter der Voraussetzung, dass die maximale Länge der zu sortierenden Schlüssel von vornherein bekannt ist, eine lineare Laufzeit. Die Vorgehensweise eines Lochkartensortierers entspricht einem Radixsort. Bei allen hier vorgestellten Varianten ist die erste Stelle des Schlüssels diejenige mit dem höchsten Rang. Man unterscheidet Verfahren, deren erster Schritt an dieser höchstwertigen Stelle (MSD) (engl. most significant digit) beginnt, dann können Teilstücke, die nach einem Verfahrensschritt weniger als zwei Elemente enthalten, im nachfolgenden Schritt übersprungen werden; und Verfahren, die an der niedrigstwertigen Stelle (LSD) (engl. least significant digit) beginnen und sich zur höchstwertigen Stelle vorarbeiten. Ferner gibt es stabile out-of-place Varianten und in-place Varianten, die jedoch nicht stabil sind.