(algorithm)
Definition: A distribution sort where input elements are initially distributed to several buckets based on an interpolation of the element's key. Each bucket is sorted if necessary, and the buckets' contents are concatenated.
Also known as bin sort.
Generalization (I am a kind of ...)
distribution sort.
Specialization (... is a kind of me.)
histogram sort, counting sort, top-down radix sort, postman's sort, distributive partitioning sort.
See also range sort, radix sort, hash heap.
Note: A bucket sort uses fixed-size buckets (or a list per bucket). A histogram sort sets up buckets of exactly the right size in a first pass. A counting sort uses one bucket per key.
The space required is one bucket for every few possible key value, but is O(n log log n) taking into account a distribution of keys. That is, some buckets will have a lot of keys.
Bucket sorts work well for data sets where the possible key values are known and relatively small and there are on average just a few elements per bucket. This means the cost of sorting the contents of each bucket can be reduced toward zero. The ideal result is if the order in each bucket is uninteresting or trivial, for instance, when each bucket holds a single key. The buckets may be arranged so the concatenation phase is not needed, for instance, the buckets are contiguous parts of an array.
Bucket sorts can be stable.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 16 November 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "bucket sort", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 16 November 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/bucketsort.html