• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 849
  • Last Modified:

Radix Sort: Why is it a good idea?

Can anyone explain to me why 'Radix sort' is a good idea (to optimize sort algorithms, potentially to compete in sorting competitions of the like found here: sortbenchmark.org) taking both memory, processor and communication abstractions into consideration?
  • 3
  • 2
1 Solution
Historical perspective is interesting.

Radix sort originated with punched card sorting machines.


The machine had an input hopper and some number (at least 10) output hoppers.  It would simply take the bottom card from the input hopper and drop it into the appropriate output hopper based on the value of some card column, set by the operator.

The operator would start with an unsorted stack of cards, and set the machine to use the least-significant digit of the sort field, the 'ones' column to separate the cards into output stacks.

Then, the operator would gather up the cards, starting with the left-most output hopper, stacking them up again, and put them back into the input hopper.  He'd then set the machine to look at the 'tens' column, and run again.  This time the cards drop based on the 'tens' digit.  Repeat for the 'hundreds' digit, etc, gathering up the output stacks each time.  Don't drop them!

When you are done, the cards are completely sorted, almost like magic.

No comparisons between cards is needed!  Each individual operation is computationally minimal.

Only one card needs to be looked at at a time!  (This is probably the most significant and UNIQUE feature of this algorithm.)
madmanneAuthor Commented:
Right so could you elaborate a bit on how this would benefit
1) memory
2) processor
3) communication

I am having a hard time separating the 3.

I think what you are saying is that the processor is having a good time? what about the others?
Memory usage is interesting.  It is good because only one record, and, in fact, only one character needs to be stored in memory at a time.  You might even say it does not need any operational  memory at all, since it looks at the key character on each card as it goes by, and immediately uses it to open the appropriate output hopper.

It does need temporary "stack" memory (equivalent to the output hoppers in the machine), which can be much cheaper than random-access memory.

The processor is interesting, because it does not need many instructions.  it does not need "compare" or any math instructions.  It only needs to be able to index on one character in memory.

Radix sort runs in predictable time.  That is, it always takes the same amount of time to sort the input data, no matter what order it was in to start with.  This is not true for other sort algorithms.  On the other hand, the disadvantage of Radix sort is that it is one of the slowest sort algorithms.

If you need more, there has been a lot written about it already, in the wikipedia for example:  http://en.wikipedia.org/wiki/Radix_sort
madmanneAuthor Commented:
And so, the communication is also kept at a minimum since everything is a local compare. Right?
You will find a more technical analysis here, with discussion of the communication aspect of Radix sort:

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now