Bucket Sort

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:

  1. Set up an array of initially empty "buckets."
  2. Scatter: Go over the original array, putting each object in its bucket.
  3. Sort each non-empty bucket.
  4. 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:

    She was a charming middle-aged lady with a face like a bucket of mud. I gave her a drink. She was a gal who’d take a drink if she had to knock me down to get the bottle.
    John Paxton (1911–1985)

    In youth, we clothe ourselves with rainbows, with hope & love, & go as brave as the zodiack. In age we put out another sort of perspiration; gout, fever, rheumatism, caprice, doubt, fretting, and avarice.
    Ralph Waldo Emerson (1803–1882)