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, a generalization of pigeonhole sort that allows multiple keys per bucket, and is a cousin of radix sort in the most-to-least significant digit flavor. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm. The computational complexity depends on the algorithm used to sort each bucket, the number of buckets to use, and whether the input is uniformly distributed.

Bucket sort works as follows:

Let array denote the array to be sorted and k denote the number of buckets to use. One can compute the maximum key value in linear time by iterating over all the keys once. The floor function must be used to convert a floating number to an integer ( and possibly casting of datatypes too ). The function nextSort is a sorting function used to sort each bucket. Conventionally, insertion sort is used due to its relatively high performance with small numbers of elements, but other algorithms could be used as well, such as selection sort or merge sort. 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).

When the input contains several keys that are close to each other (clustering), those elements are likely to be placed in the same bucket, which results in some buckets containing more elements than average. The worst-case scenario occurs when all the elements are placed in a single bucket. The overall performance would then be dominated by the algorithm used to sort each bucket, for example ${\displaystyle O(n^{2})}$ insertion sort or ${\displaystyle O(n\log(n))}$ comparison sort algorithms, such as merge sort.

Consider the case that the input is uniformly distributed. The first step, which is initialize the buckets and find the maximum key value in the array, can be done in ${\displaystyle O(n)}$ time. If division and multiplication can be done in constant time, then scattering each element to its bucket also costs ${\displaystyle O(n)}$. Assume insertion sort is used to sort each bucket, then the third step costs ${\displaystyle O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})}$, where ${\displaystyle n_{i}}$ is the length of the bucket indexed ${\displaystyle i}$. Since we are concerning the average time, the expectation ${\displaystyle E(n_{i}^{2})}$ has to be evaluated instead. Let ${\displaystyle X_{ij}}$ be the random variable that is ${\displaystyle 1}$ if element ${\displaystyle j}$ is placed in bucket ${\displaystyle i}$, and ${\displaystyle 0}$ otherwise. We have ${\displaystyle n_{i}=\sum _{j=1}^{n}X_{ij}}$. Therefore,

The last line separates the summation into the case ${\displaystyle j=l}$ and the case ${\displaystyle j\neq l}$. Since the chance of an object distributed to bucket ${\displaystyle i}$ is ${\displaystyle 1/k}$, ${\displaystyle X_{ij}}$ is 1 with probability ${\displaystyle 1/k}$ and 0 otherwise.

With the summation, it would be

Finally, the complexity would be ${\displaystyle O\left(\sum _{i=1}^{k}E(n_{i}^{2})\right)=O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}}\right)=O\left({\frac {n^{2}}{k}}+n\right)}$.