spezielles Sortierverfahren zum Sortieren von n reellen Zahlen \({x}_{1},\ldots, {x}_{n}\) aus dem Bereich (0, 1].

Das Verfahren besteht aus drei Schritten: Im ersten Schritt werden k leere Körbe bereitgestellt. Hierbei ist \(k=\alpha \cdot n\) für eine Konstante \(0\lt \alpha \le 1\). Im zweiten Schritt werden die Elemente \({x}_{1},\ldots, {x}_{n}\) sequentiell betrachtet und auf die Körbe verteilt. Das Element x_i wird in den Korb \([k\cdot {x}_{i}]\) geworfen. Damit sind für alle \(j\in \{1,\ldots, k-1\}\) alle Elemente aus Korb j echt kleiner als alle Elemente aus Korb \((j+1)\). Im dritten und letzten Schritt wird auf jeden Korb Heapsort angewendet und die so sortierten Teillisten zu einer sortierten Liste zusammengefügt.

Bucketsort muß im schlechtesten Fall wenigstens \([{\mathrm{log}}_{2}n!]\) Vergleiche ausführen. Sind die n Elemente gleichverteilt über dem Intervall (0,1], so ist die Anzahl der Schritte, die das Verfahren im Mittel ausführen muß, durch c · n für eine von n unabhängige Konstante c nach oben beschränkt.