next up previous contents index Search
Next: 0.3.10 The nth Largest Up: 0.3.9 Bucket and Radix Previous: 0.3.9 Bucket and Radix Analysis

In order to bucket sort n items in the range of 1 to m, mbuckets must be allocated, n items must be assigned to a bucket, and the contents of m buckets must be collected. The overall complexity is O(m + n) operations requiring O(m) storage locations. In contrast, in order to radix sort n items considering each key from left to right requires O(kn) time. In the preceding formula, nis the number of items to be sorted while k is the number of times the radix sort has to recurse, subdividing the contents of each bucket. As you can see, both of these algorithms have linear running time complexity.

Scott Gasch