Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Bucket sort
open-in-new
<h2 id="pseudocode">Pseudocode</h2> function bucketSort(array, k) is buckets ← new array of k empty lists M ← 1 + the maximum key value in the array for i = 0 to length(array) do insert <i>array[i]</i> into <i>buckets[floor(k × array[i] / M)]</i> for i = 0 to k do nextSort(buckets[i]) return the concatenation of buckets[0], ...., buckets[k] <p>Let <i>array</i> denote the array to be sorted and <i>k</i> denote the number of buckets to use. One can compute the maximum key value in <a href="/facts/Linear_time/77T62gmf">linear time</a> by iterating over all the keys once. The <a href="/facts/Floor_function/ssehyMMf">floor function</a> must be used to convert a floating number to an integer ( and possibly casting of datatypes too ). The function <i>nextSort</i> is a sorting function used to sort each bucket. Conventionally, <a href="/facts/Insertion_sort/N5yWe8Co">insertion sort</a> is used, but other algorithms could be used as well, such as <i><a href="/facts/Selection_sort/uIsGffcr">selection sort</a></i> or <i><a href="/facts/Merge_sort/A5jLYfzS">merge sort</a></i>. Using <i>bucketSort</i> itself as <i>nextSort</i> produces a relative of <a href="/facts/Radix_sort/ISe6XYJN">radix sort</a>; in particular, the case <i>n = 2</i> corresponds to <a href="/facts/Quicksort/1BeqhLAH">quicksort</a> (although potentially with poor pivot choices). </p> <h2 id="analysis">Analysis</h2> <h3>Worst-case analysis</h3> <p>When the input contains several keys that are close to each other (clustering), those elements are likely to be placed in the same bucket, which results in some buckets containing more elements than average. The worst-case scenario occurs when all the elements are placed in a single bucket. The overall performance would then be dominated by the algorithm used to sort each bucket, for example O ( n 2 ) {\displaystyle O(n^{2})} <a href="/facts/Insertion_sort/N5yWe8Co">insertion sort</a> or O ( n log ( n ) ) {\displaystyle O(n\log(n))} <a href="/facts/Comparison_sort/X1PvE50c">comparison sort</a> algorithms, such as <a href="/facts/Merge_sort/A5jLYfzS">merge sort</a>. </p> <h3>Average-case analysis</h3> <p>Consider the case that the input is uniformly distributed. The first step, which is initialize the buckets and find the maximum key value in the array, can be done in O ( n ) {\displaystyle O(n)} time. If division and multiplication can be done in constant time, then scattering each element to its bucket also costs O ( n ) {\displaystyle O(n)} . Assume insertion sort is used to sort each bucket, then the third step costs O ( ∑ i = 1 k n i 2 ) {\displaystyle O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})} , where n i {\displaystyle n_{i}} is the length of the bucket indexed i {\displaystyle i} . Since we are concerning the average time, the expectation E ( n i 2 ) {\displaystyle E(n_{i}^{2})} has to be evaluated instead. Let X i j {\displaystyle X_{ij}} be the random variable that is 1 {\displaystyle 1} if element j {\displaystyle j} is placed in bucket i {\displaystyle i} , and 0 {\displaystyle 0} otherwise. We have n i = ∑ j = 1 n X i j {\displaystyle n_{i}=\sum _{j=1}^{n}X_{ij}} . Therefore, </p> E ( n i 2 ) = E ( ∑ j = 1 n X i j ∑ l = 1 n X i l ) = E ( ∑ j = 1 n ∑ l = 1 n X i j X i l ) = E ( ∑ j = 1 n X i j 2 ) + E ( ∑ 1 ≤ j , l ≤ n ∑ j ≠ l X i j X i l ) {\displaystyle {\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{l=1}^{n}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}\sum _{l=1}^{n}X_{ij}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,l\leq n}\sum _{j\neq l}X_{ij}X_{il}\right)\end{aligned}}} <p>The last line separates the summation into the case j = l {\displaystyle j=l} and the case j ≠ l {\displaystyle j\neq l} . Since the chance of an object distributed to bucket i {\displaystyle i} is 1 / k {\displaystyle 1/k} , X i j {\displaystyle X_{ij}} is 1 with probability 1 / k {\displaystyle 1/k} and 0 otherwise. </p> E ( X i j 2 ) = 1 2 ⋅ ( 1 k ) + 0 2 ⋅ ( 1 − 1 k ) = 1 k {\displaystyle E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\right)+0^{2}\cdot \left(1-{\frac {1}{k}}\right)={\frac {1}{k}}} E ( X i j X i k ) = 1 ⋅ ( 1 k ) ( 1 k ) = 1 k 2 {\displaystyle E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}} <p>With the summation, it would be </p> E ( ∑ j = 1 n X i j 2 ) + E ( ∑ 1 ≤ j , k ≤ n ∑ j ≠ k X i j X i k ) = n ⋅ 1 k + n ( n − 1 ) ⋅ 1 k 2 = n 2 + n k − n k 2 {\displaystyle E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{k^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}} <p>Finally, the complexity would be O ( ∑ i = 1 k E ( n i 2 ) ) = O ( ∑ i = 1 k n 2 + n k − n k 2 ) = O ( n 2 k + n ) {\displaystyle O\left(\sum _{i=1}^{k}E(n_{i}^{2})\right)=O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}}\right)=O\left({\frac {n^{2}}{k}}+n\right)} . </p><p>The last step of bucket sort, which is concatenating all the sorted objects in each bucket, requires O ( k ) {\displaystyle O(k)} time. Therefore, the total complexity is O ( n + n 2 k + k ) {\displaystyle O\left(n+{\frac {n^{2}}{k}}+k\right)} . Note that if k is chosen to be k = Θ ( n ) {\displaystyle k=\Theta (n)} , then bucket sort runs in O ( n ) {\displaystyle O(n)} average time, given a uniformly distributed input.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> </p> <h2 id="optimizations">Optimizations</h2> <p>A common optimization is to put the unsorted elements of the buckets back in the original array <i>first</i>, then run <a href="/facts/Insertion_sort/N5yWe8Co">insertion sort</a> over the complete array; because insertion sort's runtime is based on how far each element is from its final position, the number of comparisons remains relatively small, and the memory hierarchy is better exploited by storing the list contiguously in memory.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p><p>If the input distribution is known or can be estimated, buckets can often be chosen which contain constant density (rather than merely having constant size). This allows O ( n ) {\displaystyle O(n)} average time complexity even without uniformly distributed input. </p> <h2 id="variants">Variants</h2> <h3>Generic bucket sort</h3> <p>The most common variant of bucket sort operates on a list of <i>n</i> numeric inputs between zero and some maximum value <i>M</i> and divides the value range into <i>b</i> buckets each of size <i>M</i>/<i>b</i>. If each bucket is sorted using <a href="/facts/Insertion_sort/N5yWe8Co">insertion sort</a>, the sort can be shown to run in expected linear time (where the average is taken over all possible inputs).<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> However, the performance of this sort degrades with clustering; if many values occur close together, they will all fall into a single bucket and be sorted slowly. This performance degradation is avoided in the original bucket sort algorithm by assuming that the input is generated by a random process that distributes elements uniformly over the interval <i>[0,1)</i>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p> <h3>ProxmapSort</h3> <p class="note">Main article: <a href="/facts/Proxmap_sort/Te3gaYMt">Proxmap sort</a></p> <p>Similar to generic bucket sort as described above, ProxmapSort works by dividing an array of keys into subarrays via the use of a "map key" function that preserves a partial ordering on the keys; as each key is added to its subarray, insertion sort is used to keep that subarray sorted, resulting in the entire array being in sorted order when ProxmapSort completes. ProxmapSort differs from bucket sorts in its use of the map key to place the data approximately where it belongs in sorted order, producing a "proxmap" — a proximity mapping — of the keys. </p> <h3>Histogram sort</h3> <p>Another variant of bucket sort known as histogram sort or <a href="/facts/Counting_sort/68vdcy9Y">counting sort</a> adds an initial pass that counts the number of elements that will fall into each bucket using a count array.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> Using this information, the array values can be arranged into a sequence of buckets in-place by a sequence of exchanges, leaving no space overhead for bucket storage. </p> <h3>Postman's sort</h3> <p>The Postman's sort is a variant of bucket sort that takes advantage of a hierarchical structure of elements, typically described by a set of attributes. This is the algorithm used by letter-sorting machines in <a href="/facts/Post_office/f8jr8z0E">post offices</a>: mail is sorted first between domestic and international; then by state, province or territory; then by destination post office; then by routes, etc. Since keys are not compared against each other, sorting time is O(<i>cn</i>), where <i>c</i> depends on the size of the key and number of buckets. This is similar to a <a href="/facts/Radix_sort/ISe6XYJN">radix sort</a> that works "top down," or "most significant digit first."<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <h3>Shuffle sort</h3> <p>The shuffle sort<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> is a variant of bucket sort that begins by removing the first 1/8 of the <i>n</i> items to be sorted, sorts them recursively, and puts them in an array. This creates <i>n</i>/8 "buckets" to which the remaining 7/8 of the items are distributed. Each "bucket" is then sorted, and the "buckets" are concatenated into a sorted array. </p> <h2 id="comparison-with-other-sorting-algorithms">Comparison with other sorting algorithms</h2> <p>Bucket sort can be seen as a generalization of <a href="/facts/Counting_sort/68vdcy9Y">counting sort</a>; in fact, if each bucket has size 1 then bucket sort degenerates to counting sort. The variable bucket size of bucket sort allows it to use O(<i>n</i>) memory instead of O(<i>M</i>) memory, where <i>M</i> is the number of distinct values; in exchange, it gives up counting sort's O(<i>n</i> + <i>M</i>) worst-case behavior. </p><p>Bucket sort with two buckets is effectively a version of <a href="/facts/Quicksort/1BeqhLAH">quicksort</a> where the pivot value is always selected to be the middle value of the value range. While this choice is effective for uniformly distributed inputs, other means of choosing the pivot in quicksort such as randomly selected pivots make it more resistant to clustering in the input distribution. </p><p>The <i>n</i>-way <a href="/facts/Mergesort/A5jLYfzS">mergesort</a> algorithm also begins by distributing the list into <i>n</i> sublists and sorting each one; however, the sublists created by mergesort have overlapping value ranges and so cannot be recombined by simple concatenation as in bucket sort. Instead, they must be interleaved by a merge algorithm. However, this added expense is counterbalanced by the simpler scatter phase and the ability to ensure that each sublist is the same size, providing a good worst-case time bound. </p><p>Top-down <a href="/facts/Radix_sort/ISe6XYJN">radix sort</a> can be seen as a special case of bucket sort where both the range of values and the number of buckets is constrained to be a power of two. Consequently, each bucket's size is also a power of two, and the procedure can be applied recursively. This approach can accelerate the scatter phase, since we only need to examine a prefix of the bit representation of each element to determine its bucket. </p> <ul><li>Paul E. Black <a href="https://xlinux.nist.gov/dads/HTML/postmansort.html">"Postman's Sort"</a> from <a href="/facts/Dictionary_of_Algorithms_and_Data_Structures/9jCn2VVA">Dictionary of Algorithms and Data Structures</a> at <a href="/facts/National_Institute_of_Standards_and_Technology/gr9Fnh85">NIST</a>.</li> <li>Robert Ramey <a href="http://www.rrsd.com/software_development/postmans_sort/cuj/cuj.html">'"The Postman's Sort"</a> <i>C Users Journal</i> Aug. 1992</li> <li><a href="https://xlinux.nist.gov/dads/HTML/bucketsort.html">NIST's Dictionary of Algorithms and Data Structures: bucket sort</a></li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="http://www.dcc.uchile.cl/~rbaeza/handbook/algs/4/423.sort.c.html">Bucket Sort Code for Ansi C</a></li> <li><a href="http://www1bpt.bridgeport.edu/~dichter/lilly/bucketsort.htm">Variant of Bucket Sort with Demo</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest & Clifford Stein. Introduction to Algorithms. Bucket sort runs in linear time on the average. Like counting sort, bucket sort is fast because it assumes something about the input. Whereas counting sort assumes that the input consists of integers in a small range, bucket sort assumes that the input is generated by a random process that distributes elements uniformly over the interval [0,1). The idea of bucket sort is to divide the interval [0, 1) into n equal-sized subintervals, or buckets, and then distribute the n input numbers into the buckets. Since the inputs are uniformly distributed over [0, 1), we don't expect many numbers to fall into each bucket. To produce the output, we simply sort the numbers in each bucket and then go through the buckets in order, listing the elements in each. <a href="/wiki/Thomas_H._Cormen" target="_blank">/wiki/Thomas_H._Cormen</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Corwin, E. and Logar, A. "Sorting in linear time — variations on the bucket sort". Journal of Computing Sciences in Colleges, 20, 1, pp.197–202. October 2004. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.4: Bucket sort, pp.174–177. <a href="/wiki/Thomas_H._Cormen" target="_blank">/wiki/Thomas_H._Cormen</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest & Clifford Stein. Introduction to Algorithms. Bucket sort runs in linear time on the average. Like counting sort, bucket sort is fast because it assumes something about the input. Whereas counting sort assumes that the input consists of integers in a small range, bucket sort assumes that the input is generated by a random process that distributes elements uniformly over the interval [0,1). The idea of bucket sort is to divide the interval [0, 1) into n equal-sized subintervals, or buckets, and then distribute the n input numbers into the buckets. Since the inputs are uniformly distributed over [0, 1), we don't expect many numbers to fall into each bucket. To produce the output, we simply sort the numbers in each bucket and then go through the buckets in order, listing the elements in each. <a href="/wiki/Thomas_H._Cormen" target="_blank">/wiki/Thomas_H._Cormen</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>NIST's Dictionary of Algorithms and Data Structures: histogram sort <a href="https://xlinux.nist.gov/dads/HTML/histogramSort.html" target="_blank">https://xlinux.nist.gov/dads/HTML/histogramSort.html</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>"Robert Ramey Software Development". <a href="http://www.rrsd.com/psort/cuj/cuj.htm" target="_blank">http://www.rrsd.com/psort/cuj/cuj.htm</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>A revolutionary new sort from John Cohen Nov 26, 1997 <a href="https://groups.google.com/group/fido7.ru.algorithms/msg/26084cdb04008ab3" target="_blank">https://groups.google.com/group/fido7.ru.algorithms/msg/26084cdb04008ab3</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> </ol>