RadixSort

RadixSort wird hier an einer dafür gebauten Vorrichtung aus dem 3D-Drucker erklärt. Die einzelnen Figuren entsprechen den Zahlen 0...31 und ihre Binärdarstellung (je mit 5 Bits) ist oben abgebildet:

• Ist das i-te Bit in der Zahl k an, dann ist an der i-ten Position (von rechts gelesen) der Figur eine Brücke.
• Ist das i-te Bit aus, dann ist an der i-ten Position eine Lücke.

Wird der rote Stab an Position i durch die Figuren geführt und hochgezogen, dann bleiben genau die Figuren hängen, deren i-tes Bit an ist. Zudem wird die Reihenfolge dieser Figuren nicht verändert. Setzt man die hochgezogenen Figuren nun alle hinter die liegen gebliebenen Figuren, so hat man CountingSort auf dieser Stelle ausgeführt.

Nach Schritt i=1...5 sind die Zahlen modulo 2^i korrekt sortiert. Ist Schritt i=5 abgeschlossen, so sind die Zahlen modulo 2^5 = 32 korrekt sortiert und somit insgesamt korrekt sortiert.