Motivation

Radix Sort vergleicht niemals zwei Zahlen direkt. Er gruppiert sie Ziffer für Ziffer mithilfe eines stabilen Hilfssortieralgorithmus, wodurch er die O(n log n)-Barriere durchbrechen kann, die Vergleichssortieralgorithmen nicht überwinden können.

Warum Radix Sort lernen?

• Linear-ähnliche Zeit: Er läuft in O(d * (n + k)), wobei d die Anzahl der Ziffern und k die Basis (hier 10) ist. Für Zahlen mit einer begrenzten Anzahl von Ziffern ist das effektiv O(n).
• Stabil: Gleiche Werte behalten ihre relative Reihenfolge bei, was genau das ist, was die Ziffer-für-Ziffer-Durchläufe korrekt kombinieren lässt.
• Ein anderer Ansatz: Er zeigt, dass Sortieren nicht zwangsläufig Vergleichen bedeuten muss – eine wichtige Erkenntnis für große Ganzzahlen oder Schlüssel mit fester Breite.

Der Kompromiss: Er benötigt Schlüssel, die man in Ziffern zerlegen kann (hier nicht-negative Ganzzahlen), und etwas zusätzlichen Speicher für die Buckets.