# Radix Sort visualisieren: Stelle für Stelle in Buckets

> Radix Sort (LSD) interaktiv: stabiles Counting Sort je Stelle in Basis 10 mit 10 Buckets. Linear in O(d · n) für ganzzahlige Schlüssel fester Stellenzahl.

Adresse: https://marckimmel.de/informatik/sortieralgorithmen/radix-sort
English version: https://marckimmel.de/en/informatik/sortieralgorithmen/radix-sort.md

Sortiert Stelle für Stelle in Buckets, ohne direkten Wertevergleich.

Radix Sort sortiert Zahlen Stelle für Stelle, ohne Werte direkt miteinander zu vergleichen. In der LSD-Variante (Least Significant Digit) startet der Algorithmus mit der niederwertigsten Stelle: er verteilt die Elemente in 10 Buckets (für die Ziffern 0 bis 9 im Dezimalsystem) und sammelt sie anschließend in der Bucket-Reihenfolge wieder ein. Dieser Schritt wird für jede Stelle wiederholt, bis die höchste Stelle erreicht ist. Weil das Verteilen pro Stelle stabil erfolgt, behält jede Iteration die Reihenfolge gleicher Schlüssel bei und nach der letzten Stelle ist das Array korrekt sortiert. Die Laufzeit ist O(d · (n + b)) mit d gleich der Stellenanzahl des größten Elements und b gleich der Basis (hier 10); für ganze Zahlen mit bekannter Größenordnung ist d konstant, sodass Radix Sort effektiv linear läuft. Der Speicherbedarf beträgt O(n + b) für die Buckets, und der Algorithmus ist stabil. Anwendbar nur auf nichtnegative Ganzzahlen oder Daten mit fester Stellenstruktur.

Sortieren großer Mengen ganzzahliger Schlüssel mit beschränkter Stellenanzahl, etwa Telefonnummern, Postleitzahlen oder IPv4-Adressen. Auch in Datenbank-Engines und in der String-Sortierung als MSD-Variante (Most Significant Digit) zum Einsatz.

## Weiter

- [Sortieralgorithmen](https://marckimmel.de/informatik/sortieralgorithmen.md)