Editing Bucket sort (section)

{{Short description|Sorting algorithm}}
{{Infobox algorithm
|class=[[Sorting algorithm]]
|data=[[Array data structure|Array]]
|time=<math>O\left(n^2\right)</math>
|average-time=<math>O\left(n+\frac{n^2}{k}+k\right)</math>, where k is the number of buckets. <math>O(n), \text {when } k \approx n</math>.
|space=<math>O(n + k)</math>
}}

[[File:Bucket sort 1.svg|right|frame|Elements are distributed among bins]]
[[File:Bucket sort 2.svg|right|frame|Then, elements are sorted within each bin]]
'''Bucket sort''', or '''bin sort''', is a [[sorting algorithm]] that works by distributing the elements of an [[Array data structure|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]],  a generalization of [[pigeonhole sort]] that allows multiple keys per bucket, and is a cousin of [[radix sort]] in the most-to-least significant digit flavor. Bucket sort can be implemented with comparisons and therefore can also be considered a [[comparison sort]] algorithm. The [[Analysis of algorithms|computational complexity]] depends on the algorithm used to sort each bucket, the number of buckets to use, and whether the input is uniformly distributed.

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.