Re:Nice and all (Score 1)

Another example:, quicksort is poor at sorting strings. This is because you have to perform a full strcmp() (or equivalent) at each comparison. For this reason, a modified radix sort is often used.

Radix sort is also not very good at sorting strings. Radix sort requires O(nk) where k equals the number of radix points. If one sorts a list names from the phone book, the keys in this case can have over 30 radix points. Since 2^32 is over 4 billon a quicksort can sort better than a radix sort as long as there are less than 1 billon names to be sorted in this case.

Also strcmp is not that slow over all. Since there are far far more people not named John Smith then there are that are named John Simth, strcmp() will complete the vast majority of it's calls in just a few operations.

Radix sort can not be done in place, thus requiring double the memory to run (will at least for the pointers which for a large list can still be quite a cost). If this addition memory needs to be swapped in and out the performance penalty can be quite nasty.

Radix sort is best used when the number of radix points is quite small such as zip codes (only 5 radix points). In general this only happens when a large number of items have only a few keys. This prevents radix sort from being a good general purpose sort.

Quicksort with a good pivot selection algorithm (to avoid the already sorted list problem) or Mergesort are still used quite often today.
In fact the Java library sort uses a modified mergesort, and the standard C library has qsort().

I did check Knuth about this, and radix sort can get around its problems with a beefy machine. I did some checking and in fact radix is standard for supercomputers. So if you are programming a Cray or whatever they call them now days you can ignore everything I have said.