Bucket sort, or bin sort, is a sorting algorithm that works by partitioning 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. Since bucket sort is not a comparison sort, the Ω(n log n) lower bound is inapplicable. The computational complexity estimates involve the number of buckets.
Bucket sort works as follows:
- Set up an array of initially empty "buckets."
- Scatter: Go over the original array, putting each object in its bucket.
- Sort each non-empty bucket.
- Gather: Visit the buckets in order and put all elements back into the original array.
Read more about Bucket Sort: Pseudocode, Optimizations, Comparison With Other Sorting Algorithms
Famous quotes containing the words bucket and/or sort:
“Dear fellow-artist, why so free
With every sort of company,
With every Jack and Jill?
Choose your companions from the best;
Who draws a bucket with the rest
Soon topples down the hill.”
—William Butler Yeats (1865–1939)
“Nietzsche, to the end of his days, remained a Russian pastor’s son, and hence two-thirds of a Puritan; he erected his war upon holiness, toward the end, into a sort of holy war.”
—H.L. (Henry Lewis)