Bucket Sort eignet sich für den Fall, dass der Wertebereich, in dem sich die zu sortierenden Zahlen befinden, einigermaßen eng begrenzt ist.
Beispielsweise möchte ein Verein aus Anlass der bevorstehenden 100-Jahr-Feier die Mitgliederkartei nach Jahren der Vereinszugehörigkeit sortieren. Dann kommen als mögliche Werte nur Zahlen zwischen 0 und 99 vor.
Das Sortierverfahren Bucket Sort funktioniert so: Es werden 100 Eimer (engl.: bucket) aufgestellt und mit den Zahlen von 0 bis 99 nummeriert. Die Karteikarten werden nun eine nach der anderen in die Eimer geworfen, wobei eine Karte bei k-jähriger Mitgliedschaft in den Eimer mit der Nummer k kommt. Am Ende werden die Eimer, beginnend bei Nummer 0, der Reihe nach wieder ausgeleert. Auf diese Weise ergibt sich die nach Jahren der Vereinszugehörigkeit sortierte Mitgliederkartei.
Jede der n Karteikarten wird genau einmal in einen Eimer geworfen und genau einmal wieder entnommen. Die Komplexität von Bucket Sort liegt also in Θ(n).
Die Eimer werden als Array list von verketteten Listen dargestellt. Das Werfen einer Karteikarte in den Eimer Nummer k wird implementiert, indem ein Verweis auf die Karteikarte in die Liste list[k] eingefügt wird.
Nachteilig bei dem eben geschilderten Beispiel ist der relativ hohe Aufwand von 100 Eimern. Stehen nur 10 Eimer zur Verfügung, so lassen sich die Karteikarten immerhin in zwei Durchläufen von Bucket Sort sortieren. Im ersten Durchlauf werden die Karten nach Jahrzehnten der Mitgliedschaft grob sortiert. Im zweiten Durchlauf werden die Karten, getrennt für jedes Jahrzehnt, nach Jahren sortiert.
Wären Werte bis 999 möglich gewesen, so hätten die Karten zuerst nach Jahrhunderten, dann nach Jahrzehnten und dann nach Jahren sortiert werden müssen; es wären also drei Durchläufe von Bucket Sort erforderlich gewesen.
Dieses Verfahren heißt Radix Sort. Die Bezeichnung Radix Sort rührt daher, dass die zu sortierenden Zahlen zur Basis b (engl.: radix b) dargestellt werden, wobei b die Anzahl der zur Verfügung stehenden Eimer ist. Für jede Stelle der Zahlendarstellung wird dann ein Durchlauf von Bucket Sort durchgeführt.
Sind allgemein w die Anzahl der möglichen Werte und b die Anzahl der Eimer, so sind logb(w) Durchläufe erforderlich. Jeder Durchlauf benötigt Θ(n) Schritte, wenn n die Anzahl der zu sortierenden Daten ist.
Ist die Anzahl b der Eimer konstant, so ergibt sich für Radix Sort eine Komplexität von Θ(n log(w)).
Da die Daten im Computer in Binärdarstellung vorliegen, bietet es sich an, mit b = 2 zu arbeiten. Implementiert wird Radix Sort meist so, dass zuerst nach dem niederwertigsten Bit 0 sortiert wird. Im nächsten Durchlauf wird der gesamte Datensatz nach Bit 1 sortiert, jedoch ohne dabei die Reihenfolge von Zahlen mit gleichem Bit 1 zu verändern, usw.
Folgendes Bild zeigt ein entsprechendes Vorgehen für den Fall b = 10. Zuerst wird die Folge nach der letzten Ziffer sortiert, dann nach der zweiten, dann nach der ersten.
| 305 | 123 | 013 | 130 | 725 | 612 | 122 | 123 |
| 130 | 612 | 122 | 123 | 013 | 123 | 305 | 725 |
| 305 | 612 | 013 | 122 | 123 | 123 | 725 | 130 |
| 013 | 122 | 123 | 123 | 130 | 305 | 612 | 725 |
Weiter: [Median-Algorithmus] oder [up]