An analysis and implementation of an efficient in-place bucket sort

摘要

Variosu methods, such as address-calculation sorts, distribution counting sorts, radix sorts, and bucket sorts, use the values of the numbers being sorted to increase efficiency but do so at the expense of requiring additional storage space. In this paper, a specific implementation of bucket sort is presented whose primary Advantanges are that (I) linear average-time performance is achieved with an additional Amount of storage equal to any fraction of he number of elements being sorted and (ii) no linked-list data structures are used (all sorting is done with arrays).