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?
madmanneAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

sjklein42Commented:
Historical perspective is interesting.

Radix sort originated with punched card sorting machines.

http://www.technikum29.de/shared/photos/rechnertechnik/ibm_083.jpg

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.)
0
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?
0
sjklein42Commented:
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
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
madmanneAuthor Commented:
And so, the communication is also kept at a minimum since everything is a local compare. Right?
0
sjklein42Commented:
You will find a more technical analysis here, with discussion of the communication aspect of Radix sort:

http://webcache.googleusercontent.com/search?q=cache:7x6zS8d9_PgJ:pages.cs.wisc.edu/~dusseau/Papers/sort.ps+&cd=10&hl=en&ct=clnk&gl=us
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Project Management

From novice to tech pro — start learning today.