Bucket sort

Bucket sort

Class	Sorting algorithm
Data structure	Array
Worst-case performance	${\displaystyle O(n^{2})}$
Best-case performance	${\displaystyle \Omega (n+k)}$
Average performance	${\displaystyle \Theta (n+k)}$
Worst-case space complexity	${\displaystyle O(n\cdot k)}$

Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm. The computational complexity estimates involve the number of buckets.

Bucket sort works as follows:

Here array is the array to be sorted and n is the number of buckets to use. The function msbits(x,k) returns the k most significant bits of x (floor(x/2^(size(x)-k))); different functions can be used to translate the range of elements in array to n buckets, such as translating the letters A–Z to 0–25 or returning the first character (0–255) for sorting strings. The function nextSort is a sorting function; using bucketSort itself as nextSort produces a relative of radix sort; in particular, the case n = 2 corresponds to quicksort (although potentially with poor pivot choices).

Note that for bucket sort to be ${\displaystyle O(n)}$ on average, the number of buckets n must be equal to the length of the array being sorted, and the input array must be uniformly distributed across the range of possible bucket values. If these requirements are not met, the performance of bucket sort will be dominated by the running time of nextSort, which is typically ${\displaystyle O(n^{2})}$ insertion sort, making bucket sort less optimal than ${\displaystyle O(n\log(n))}$ comparison sort algorithms like Quicksort.

...
Wikipedia