Bucketsort
# Bucketsort

Bucketsort (von englisch bucket „Eimer“) ist ein Sortierverfahren, das für bestimmte Werte-Verteilungen eine Eingabe-Liste in linearer Zeit sortiert. Der Algorithmus ist in drei Phasen eingeteilt:
* Verteilung der Elemente auf die Buckets (Partitionierung)
* Jeder Bucket wird mit einem weiteren Sortierverfahren wie beispielsweise Mergesort sortiert.
* Der Inhalt der sortierten Buckets wird konkateniert.
Das Verfahren arbeitet also out-of-place.

## Algorithmus

Die Eingabe von Bucketsort ist eine Liste $l$ mit $n$ Elementen und eine Funktion $f$, die jedes Element der Liste in das halboffene Intervall $[0,1[$ monoton in der Weise abbildet, dass $f(e)\leq f(e^{\prime })$ für $e$ sortiermäßig $\prec e^{\prime }$. Basiert die Sortierreihenfolge $\prec$ auf einem Vergleich binärer Daten, kann man die Bits mit der höchsten Signifikanz nehmen. Während der Sortierung verwendet der Algorithmus $k$ „Buckets“, die in einem Array angeordnet sind. Die Verteilung der Elemente geschieht über dieses Array, indem jedes Element $e$ in den $\lfloor f(e)\cdot k\rfloor$-ten Bucket gelegt wird. Danach wird nacheinander jeder Bucket sortiert. In der letzten Phase werden die Bucket-Listen in der Reihenfolge, wie sie im Array angeordnet sind, konkateniert, was als Ergebnis die sortierte Ausgabe darstellt.
Als Pseudo-Code:
Der Algorithmus sortiert stabil, wenn der für die Sortierung der Buckets verwendete Sortier-Algorithmus, hier mergesort, stabil ist.

## Komplexität

Die Verteilung der Funktionswerte von $f$ bestimmt die Laufzeit von Bucketsort. Die Laufzeit ist in ${\mathcal {O}}(n)+\sum _{i=0}^{k-1}{\mathcal {O}}(l_{i}\log l_{i})$ (in O-Notation), wobei $l_{i}$ die Anzahl der Elemente im $i$-ten Bucket bezeichnet. Bei einer Gleichverteilung ist die Gesamtlaufzeit in ${\mathcal {O}}(n)$, da die Summe über die Buckets linear ist und ihre Summanden als konstant (bei exakter Gleichverteilung =1) angesehen werden können. Die effiziente Laufzeit von ${\mathcal {O}}(n)$ ist nicht nur bei einer Gleichverteilung gegeben, sondern bei allen Verteilungen, nach denen der Summenterm asymptotisch linear ist. Sie wird auch als Average-Case-Laufzeit angesehen.
Bei anderen Werte-Verteilungen kann die Laufzeit des Bucketsortalgorithmus von der Laufzeit des Sortier-Algorithmus dominiert werden, der zur Sortierung eines Buckets verwendet wird. Ein solcher Worst-Case tritt beispielsweise ein, wenn alle Elemente einem einzigen Bucket zugeordnet werden. Bei Verwendung von mergesort für die Sortierung der Buckets ist die Gesamtlaufzeit dann in ${\mathcal {O}}(n\log n)$.
Natürlich lässt sich diese Sortierung zweiter Stufe wieder als Bucketsort implementieren, dann mit Sub-Buckets pro Bucket. Diese Vorgehensweise ist im Artikel Radixsort beschrieben und ist eine Form des MSD Radixsort.
Der Speicherbedarf liegt in ${\mathcal {O}}(n)$.