Editing Bucket sort (section)

===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>