• 01-05-2003
ripper079
Hello everbody,

didnīt really know where to post this thread but I think here would be the best place (for me :) ). Iīve been trying to figurate out when to implement Radix Sort. From my knowledge this is a very powerful algorithm that works only with numbers (I think???) and I canīt really se any downside with it except maybe for the memory consumtion with large numbers? Isnīt this the ultimate sorting algorithm (for numbers)???

My simple qustion is: When should I use Radix Sort?
• 01-05-2003
Prelude
>Isnīt this the ultimate sorting algorithm (for numbers)???
No, I believe Quicksort has that title for the time being. And Radix sorts work with binary numbers, they can be used for non-numerical data as well. ;)

>When should I use Radix Sort?
When it works best for your needs. Just like any sorting algorithm you choose the best combination of speed, stability, simplicty, and potential worst case for your particular problem.

-Prelude
• 01-05-2003
Nick
Quote:

And Radix sorts work with binary numbers, they can be used for non-numerical data as well.
Depends on what you use for the stable sort for each digit.
If you use counting sort then I don't see any *easy* way to get that sort to use non-numerical data.

Quote:

I canīt really se any downside with it except maybe for the memory consumtion with large numbers? Isnīt this the ultimate sorting algorithm (for numbers)???
There is alot of copying if you use counting sort also.
• 01-05-2003
FillYourBrain
prelude, not sure what you would use as criteria for "ultimate sort algorithm" but radix is faster than quick sort (for the cases it can be used) by a substantial margin. Where I can use radix I do.
• 01-05-2003
Nick
Quote:

prelude, not sure what you would use as criteria for "ultimate sort algorithm" but radix is faster than quick sort (for the cases it can be used) by a substantial margin. Where I can use radix I do.
Plain quicksort, maybe, but I doubt, on average, you can get faster then quicksort with the following provisions
1. removing one level of recursion
2. insertion sort for small cases.

Radix sort can be made to run in O(n) worse case, much faster
than O(n^2) quicksort's worse case but the extra copying slows
it down.
• 01-06-2003
FillYourBrain
copying isn't much of a factor if you use pointers. Radix is faster. Quicksort has only the advantage of being more generic and usable on more types.