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[0]...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.