I sugest you read Radix Sort Revisited.

The textbook for my digital systems class claims that while radix sort looks faster than qsort on paper, you have to really look out for cache misses since they will ruin your performance. Qsort does better in practice for data sets that are prone to cache misses because it has better temporal coherence.

Of course this was from a discussion of classic radix sort. You might do better with a revised algorithm (or not).

My 2c.

QSort is the best (single-threaded) algorithm there is for sorting arbitrarily ordered data without any restrictions. (nothing can be faster than O(n*log(n)) for non-sorted elements) (I believe there are mergesorts that are slightly faster in their best case, but they are overly optimized and so hacked into oblivion that it is not worth going for them)

Radix if I'm not mistaken "is" faster because of the fact, that there is an invariant that needs to be met... which is, you must know in which range your elements are in, meaning, that you no longer sort, but group, as you are expecting 10 groups, but have e.g. 1000 elements, this can be done in one go. But then you must only have index from 0-9 too, so this would perhaps be useful for sorting by shaders (the same shade is commonly used many many times).

(the only real use for bubblesort, or the prefered insertionsort is when you have a sorted list with VERY FEW unsorted elements, that is, perhaps 1-4 in 10000 elements, but then again, if that wouldn't be the case your screwed... big time)

EDIT: as the text says, nothing can actually have lower complexity than O(n*log(n)), just make less passes or do them faster (such as msort/qsort). All other sorting techniques rely on very strong/unusual invariants.

You are mistaken. Radix sort is O(n). Saying that it's not a sort is silly. But complexity is not the only thing that determines sort performance (caching, in particular, matters). That was my point.

Well in a way you are wrong, because Radix is not sorting per definition, as I said, it requires a very strong invariant which can only be satisfied in very few cases, that is, when you have many many elements, but only a few unique, you cannot sort arbitrary data with it. So really, one cannot even compare Radix and Qsort.

EDIT: e.g. you cannot sort a phonebook using radix.

Sure I can. Just turn the names into base 27 numbers, with each letter representing a digit and the space character representing a digit.

Trust me on this one, I've gone courses on it.

Quote from the Radix paper
"That’s why this sort routine breaks the theoretical lower bound of the O(N*logN) complexity"

with other words, nothing can _SORT_ faster than O(n*log(n))

How come Radix can? Because it isn't comparing or sorting, it is _grouping_ data, and to do that it needs a predefined number of groups.

In your case you would have base 27 right? Yes you can sort on that... but let's see what happens

if you want a 10 character limit, you will get 27^10 as the number of groups (all possible strings with 10 characters at most in it)... 205891132094649 ... oh dear, that's quite the number... let's see, and then multiply by AT LEAST 4 bytes per pointer (should be more for counting etc) 823564528378596 ... hmm, that is 823TB of memory needed (without the strings) ...

And indeed, regardless of sorting 1 string, or 2 strings, you would still have to traverse the ENTIRE list to get the sorted list out... which would pretty much take forever. (and still we have a 10 letter limit)

Do you still think you can _SORT_ with radix?
No you cannot, what you for instance CAN do however is to Radix sort by the first letter, and then Qsort the groups, don't know if there is any gain though.

As the text says, and the mathematicians says, "nothing can _SORT_ faster than O(n*log(n))", it has been mathematically proven, however, you can group data faster.

Which is what Radix does, the condition for usage of radix is like grouping all the worls people by age, as you would have about 100 groups, and many million people it would be extremely fast, but not sorting a phonebook, because there is no group limit, and also no use of it.

Sorting arbitrary data is best done using qsort/msort.
Sorting very limited range data is best done using Radix.

EDIT: in regard to the initial post, sorting tens of thousands of polygons using RADIX is very likely done using approximation, meaning, you round the distance off to only cover a small area e.g. 0-255, thus getting vicious speed, and decent sorting, but not perfect, but good enough to be used by the GPU to draw them in almost front-to-back order.

[Edited by - Syranide on June 29, 2005 7:10:56 AM]