Radix Sort...

[Boosted2k2]

I did a bunch of implementations of sorting methods for a class. I did Radix straight sort, mergesort, quicksort, and selection sort. I get the performance I expect out of all of the sorting methods except for Radix Sort. I does act linear O(n), but it takes longer than all of the other methods excluding selectionsort.

Only at 15,000,000 elements does Quicksort become slower than Radix. A comparison between Mergesort and Radixsort shows that Mergesort is (almost linearly) 2 times faster than Radix Straight.

In all cases... all sorting methods are sorting the same exact unsorted array (all integers). Due to the way that the random numbers are generated, the radix (length of max number) is 5. The radix sort is implemented using queues. The queues I am using are implemented using circular arrays. I've also tried queues as linked lists. As expected... that is even slower than using circular arrays.

I think the time difference comes from enqueueing and dequeueing single elements from the queue. That would mean that to sort 500,000 elements, with a radix of 5... requires 5,000,000 function calls total to complete the sort. That is the same regardless of whether the queue is implemented with a linked list or a circular array. The only way I can get time to be somewhat comparative with mergesort, would to have a entire queue dequeued in a single call. But the problem is that is not how a true ADT queue should work. It should only remove/add one item at a time.

I have only come across one page on the internet that says Radix sucks and it's slow sometimes.

Ahhhh... Finally THE QUESTION lol: Algorithms and theoretical complexity doesn't account for overhead. Does it sound right that Radix straight sort is taking longer than mergesort (all sorting integer values) due to the amount of overhead involved?

I can't think of any other better (while still being "correct") way of implementing these. Hoping there is someone here who has compared these algorithms that might be able to confirm or deny this. Or offer a suggestion.

Thanks in advance.
Alex


TODO:
[ x ] eat
[ x ] sleep
[ x ] breath
[ ] Learn to make shorter posts

[KevinHall]

Check out this post. Pay special attention to the last paragraph.