What is the difference between bucket sort and radix sort?

algorithm language-agnostic sorting radix-sort bucket
Lazarus picture Lazarus · Dec 16, 2010 · Viewed 44.6k times · Source

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

Akash picture Akash · Jan 6, 2011

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.

Related questions

In-Place Radix Sort

This is a long text. Please bear with me. Boiled down, the question is: Is there a workable in-place radix sort algorithm? Preliminary I've got a huge number of small fixed-length strings that only use the letters “A”, “C”, “G” …

Read More
How can I pair socks from a pile efficiently?

Yesterday I was pairing the socks from the clean laundry and figured out the way I was doing it is not very efficient. I was doing a naive search â€” picking one sock and "iterating" the pile in order to find …

Read More
What is stability in sorting algorithms and why is it important?

I'm very curious, why stability is or is not important in sorting algorithms?

Read More