Editing Bucket sort (section)

==  Variants  ==

===Generic bucket sort===
The most common variant of bucket sort operates on a list of ''n'' numeric inputs between zero and some maximum value ''M'' and divides the value range into ''b'' buckets each of size ''M''/''b''. If each bucket is sorted using [[insertion sort]], the sort can be shown to run in expected linear time (where the average is taken over all possible inputs).<ref>[[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&ndash;177.</ref> 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 ''[0,1)''.<ref name="lfcs">{{cite book|title=[[Introduction to Algorithms]]|author=Thomas H. Cormen|author-link=Thomas H. Cormen|author2=Charles E. Leiserson|author2-link=Charles E. Leiserson|author3=Ronald L. Rivest|author3-link=Ronald L. Rivest|author4=Clifford Stein|author4-link=Clifford Stein|name-list-style=amp|quote=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.}}</ref>

===ProxmapSort===
{{Main article|Proxmap sort}}
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.

===Histogram sort===
Another variant of bucket sort known as histogram sort or [[counting sort]] adds an initial pass that counts the number of elements that will fall into each bucket using a count array.<ref>[https://xlinux.nist.gov/dads/HTML/histogramSort.html NIST's Dictionary of Algorithms and Data Structures: histogram sort]</ref> 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.{{Failed verification|date=September 2020}}

===Postman's sort===<!-- This section is linked from [[Radix sort]] -->
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 [[post office]]s: 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(''cn''), where ''c'' depends on the size of the key and number of buckets. This is similar to a [[radix sort]] that works "top down," or "most significant digit first."<ref>{{Cite web|url=http://www.rrsd.com/psort/cuj/cuj.htm|title = Robert Ramey Software Development}}</ref>

===Shuffle sort===<!-- This section is linked from [[J sort]] -->
{{Main article|Shuffle sort}}

The '''shuffle sort'''<ref>[https://groups.google.com/group/fido7.ru.algorithms/msg/26084cdb04008ab3 A revolutionary new sort from John Cohen Nov 26, 1997]</ref> is a variant of bucket sort that begins by removing the first 1/8 of the ''n'' items to be sorted, sorts them recursively, and puts them in an array. This creates ''n''/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.