|
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.
|
Search