How it works?

Radix Sort verarbeitet jeweils eine Ziffernposition, von der niederwertigsten (Einerstelle) bis zur höchstwertigen. Jeder Durchlauf verwendet eine stabile Sortierung, damit die Arbeit der vorherigen Durchläufe erhalten bleibt.

Schritt-für-Schritt-Prozess:

1. Nach der Einerstelle sortieren unter Verwendung eines stabilen Counting Sorts.
2. Nach der Zehnerstelle sortieren, wobei die vorherige Reihenfolge bei Gleichstand beibehalten wird.
3. Fortfahren für die Hunderter, Tausender und so weiter, bis die Ziffernposition der größten Zahl verarbeitet wurde.

Beispiel für [170, 45, 75, 90, 2, 802, 24, 66]:

• Nach Einerstelle: [170, 90, 2, 802, 24, 45, 75, 66]
• Nach Zehnerstelle: [2, 802, 24, 45, 66, 170, 75, 90]
• Nach Hunderterstelle: [2, 24, 45, 66, 75, 90, 170, 802]

Nach der letzten Ziffer ist das Array vollständig sortiert. Das Besondere ist, dass die Stabilität die Reihenfolge der niedrigeren Ziffern intakt hält, während die höheren Ziffern übernehmen.