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).Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 8.4: Bucket sort, pp.174–177. 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).
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).Thomas H. Cormen, Charles E. Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 8.4: Bucket sort, pp.174–177. 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).