Radixsort, spezielles Sortierverfahren zum Sortieren von n Wörtern x₁,…,x_n über einem endlichen, bzgl. einer binären Relation ≤ total geordneten Alphabet Σ der Größe m.

Die Relation ≤ sei hierbei auf das freie Monoid Σ^* aller endlichen Wörter über Σ fortgesetzt. Es gelte genau dann x_i ≤ x_j, wenn entweder x_i ein Präfix von x_j ist, oder es Wörter z, u₁, u₂ ∈ Σ^* und zwei Zeichen a, b ∈ Σ mit x₁ = z · a · u₁, x₂ = z · b · u₂ und a< b gibt. Der binäre Operator · steht hierbei für die Konkatenation zweier Wörter.

Das Verfahren stellt in einem ersten Schritt m freie Fächer F[1],…,F[m] bereit, die als Listen realisiert sind. In dem zweiten Schritt werden die Wörter x₁,…,x_n über l_max Iterationen sortiert, wobei l_max die Länge des längsten Wortes der Wörter x₁,…,x_n angibt. In der j-ten Iteration wird jedes x_i, beginnend bei x₁, betrachtet, und in das Fach F[x_{i, lmax}−j+1] geworfen, d.h., hinten an das Fach F[x_{i, lmax}−j+1] angefügt. Hierbei bezeichnet x_{i, j} das j-te Zeichen des Wortes x_i. Ist die Länge von x_i kleiner als j, so ist x_{i, j} gleich dem leeren Wort ε, das nach Definition kleiner als jedes Zeichen a ∈ Σ ist.

Nach diesem Verteilen in die Fächer werden diese, beginnend beim ersten Fach, bis hin zum m-ten Fach aufgesammelt und wieder zu einer Liste zusammengefügt. Durch die Festlegung, daß beim Verteilen in die Fächer die Elemente jeweils hinten an ein Fach angefügt werden, ist das Verfahren ein stabiles Sortierverfahren. Somit sind nach der j-ten Iteration die Wörter x₁,…,x_n nach den Teilwörtern \begin{eqnarray}{x}_{i,l}{{}_{{}_{\max}}}_{-j+1}\cdot {x}_{i,l}{{}_{{}_{\max}}}_{-j+2}\cdots {x}_{i,l}{}_{{}_{\max}}\end{eqnarray} sortiert.