  ## Encyclopedia > Bucket sort

Article Content

# Bucket sort

Bucket sort is a sort algorithm that works by partitioning an array into a finite number of buckets and then sorting each bucket. It is a generalization of pigeonhole sort. Bucket sort runs in linear time when input is drawn from a uniform distribution.

It works as follows:

1. Set up an array of initially empty "buckets" the size of the range.
2. Go over the original array, putting each object in its bucket.
3. Sort each non-empty bucket.
4. Put elements from non-empty buckets back into the original array.

### Pseudocode

``` ' A is the array
' n is the number of buckets
' MSBITS(n) returns the most significant bits of n.
'    This could be k*n for sorting numbers, or
'    the first character of n for sorting strings.
' NEXT-SORT is a sort algorithm
BUCKET-SORT(A, n, MSBITS, NEXT-SORT):
make array B of n lists
for i = 1 to n:
insert A[i] into list B[MSBITS(A[i])]
for i = 0 to n - 1:
NEXT-SORT(B[i])
concatenate the lists B...B[n-1] in order
```

### Relationships to other sorting algorithms

Using BUCKET-SORT itself as the NEXT-SORT produces a relative of the radix sort. Using BUCKET-SORT with n == 2 and itself as the NEXT-SORT produces quicksort.

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 Michael Barrymore ... Barrymore, born 4 May 1952, is a British comedian famous for his variety shows. This article is a stub. You can help Wikipedia by fixing it. Early ...  