Bucket Sort

Es folgt ein Sortierverfahren, welches ohne Vergleichen arbeitet und daher die Voraussetzungen für die Ableitung der untere Schranke $O(n\cdot \log n)$ nicht erfüllt und sie daher unterbieten kann. BucketSort sortiert einen endlichen, zuvor bekannten Schlüsselbereich durch Verteilen auf Buckets. Eine Erweiterung dieser Idee für das Sortieren von Strings führt zum Sortierverfahren RadixSort, welches hier nicht behandelt wird.

Source: BucketSort.java     JavaDoc: BucketSort.html     Applet: