Bucketsort

Bucketsort (von engl. 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:

1. Verteilung der Elemente auf die Buckets (Partitionierung)
2. Jeder Bucket wird mit einem weiteren Sortierverfahren wie beispielsweise Insertionsort sortiert.
3. Der Inhalt der sortierten Buckets wird konkateniert.