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:

    And now, far removed from the loved habitation,
    The tear of regret will intrusively swell,
    As fancy reverts to my father’s plantation,
    And sighs for the bucket that hung in the well.
    Samuel Woodworth (1788–1842)

    There are a sort of men whose visages
    Do cream and mantle like a standing pond,
    And do a willful stillness entertain,
    With purpose to be dressed in an opinion
    Of wisdom, gravity, profound conceit,
    As who should say, “I am Sir Oracle,
    And when I ope my lips let no dog bark!”
    William Shakespeare (1564–1616)