Bucket Sort

BucketSort is a family of sorting algorithms which divide an array into buckets of related values, sort each bucket with some other sorting algorithm, and then concatenates them.

MSD RadixSort is often a form of BucketSort.

BucketSort's WorstCase? performance is O(n^2), its average case is O(n+k), and its space complexity is O(n*k), where k is the number of buckets. In a well-implemented BucketSort, however, the can drop to O(n + k) by allocating only enough space to hold every element in the array, then storing pointers to where each bucket starts.

CountingSort is a specialisation of BucketSort where the size of each bucket is always one.