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.