algorithm - What is the difference between bucket sort and radix sort?

Question

Bucket sort and radix sort are close cousins; bucket sort goes from MSD to LSD, while radix sort can go in both "directions" (LSD or MSD). How do both algorithms work, and in particular how do they differ?

Answer 1

The initial pass of both RadixSort and BucketSort is exactly the same. The elements are put in buckets (or bins) of incremental ranges (e.g. 0-10, 11-20, ... 90-100), depending on the number of digits in the largest number.

In the next pass, however, BucketSort orders up these 'buckets' and appends them into one array. However, RadixSort appends the buckets without further sorting and 're-buckets' it based on the second digit (ten's place) of the numbers. Hence, BucketSort is more efficient for 'Dense' arrays, while RadixSort can handle sparse (well, not exactly sparse, but spaced-out) arrays well.