Radix Sort Revisited
codercorner.com
codercorner.com
I haven't even gotten to his bits about floats and negative floats, which I will assume for now are very clever. But his basic grasp of basic undergraduate algorithmics is a little... idiosyncratic.
The author defines "radix" incorrectly. "Radix" is a synonym for "base", in the sense used in "base 16" or "base 10" or "base twenty six".
The author's first pass at explaining radix sort (up to "Radix sort is stable by the way") is not radix sort at all, it's counting sort. Admittedly, I suspect that any good explanation of radix sort will start by teaching some stable linear-time sort, probably counting sort (but alternately bucket sort).... but that doesn't mean that they're the same algorithm.
Then, up to the section marked Sorting Floating Point Values, he actually explains radix sort. This part seems okay to me.
His analysis of the running time is atrocious... for one thing, he doesn't distinguish between his counting-sort phase and his radix-sort phase, which makes it a bit hard to illustrate exactly where he's being silly, but... First, counting sort takes O(n * R), where R is the size of the range of input values (R is known as the "radix", remember). In his case this is implicitly 256, which he appears to equate to 1 (yes, they're asymptotically equivalent if it's always 256, but in my opinion 256 is a large enough constant factor to be worthy of note). In a more general algorithm, this radix should be seen as a parameter of the analysis. Of course, he indirectly addresses this in his section about "extending to words or dwords" (i.e. his section on actual radix sort), but it would be better to be explicit about it.
Further, radix sort does d passes, each taking O(n * R), where d is the number of digits and R is still the Radix. What's the largest value? It's around R^d. So if you want to sort digits with a maximum of M, you need d=log_R(M). If you assume that your range of values is at least as large as your set of values (you have n values, remember), then you need log(n) passes of time O(n), in other words it takes, on the whole O(n logn). The only way to beat this is when you're sorting values which live in a smaller domain than the value-set, like say this list:
[3, 4, 5, 5, 2, 3, 3, 2, 6, 6, 2, 1, 4, 1, 1, 6, 6, 4, 3, 2]
Oh, and while I'm kvetching, he writes O(4 * n), which is just a weird thing to write. It's not technically wrong (since after all O(n) and O(4 * n) each refer to sets of functions, and the sets they refer to are co-extensional), but it's a "code smell".
So. In summary, he uses a lot of sloppy terminology, is sloppy about separation of concerns, and fails to actually analyze the actual runtime complexity of his algorithm, except that in a special case he turns out to be coincidentally correct.
Also note, btw, that this article was last edited in 2000 (er, plus a footnote in 2007). But no big deal: the article isn't "news", so it doesn't really matter that it's old; the content of this article, and my criticisms thereof, are neither more nor less relevant now than they were in 2000.
EDITS: lots of (minor) edits in the first 10 minutes of being posted, mostly formatting
I do approve of the bit on sorting floats, and sorting negative floats. Basically, his approach here is "don't be afraid of IEEE floats, just read the damn format and use your brain and do the work". Absolutely. I mean, I assume every reader of this comment is, in the case of sorting, better off using library routines, but I approve of the general principle.
His section on "reducing the complexity" is, while factually correct, basically trivial and a waste of reading time. Unless you work in an incredibly constrained environment, in a very primitive language, with no libraries. In which case, okay, that's good trick.
The bit on "Temporal Coherence"... sigh. First of all, I have never heard of this name ("temporal coherence") for this property. Maybe that's my fault? The property (of performing well on sorted input) is interesting, but it's even more interesting to perform well on nearly-sorted data. Go look at insertion sort for small data, or timsort for large data. (Or just use timsort for everything all the time, honestly). His optimization costs an extra n comparisons, and occasionally saves a lot of time but mostly saves no time. Whether it's worth it depends on your expected input data. I dunno, I'm not impressed.
As for his "nice side effect of temporal coherence", I confess I didn't entirely understand his example, as evidence by the fact that I'm doubtful that his code sample works, but either way the property is already achieved by your choice of:
* any stable sort * any library sorting routine that doesn't completely suck
So, touting this as a special benefit is a little stupid. I think. Unless I missed his point here, which I probably did.
His Applications section is just stupid. I don't need suggestions on what I could use a sort for.
O(n + R), actually: http://en.wikipedia.org/wiki/Counting_sort#Analysis
I agree that he overstates radix sort though. Asymptotically it just changes the runtime from O(n log n) (ala quicksort) to O(n log k) where k is the size of the set of possible numbers, and usually n is smaller than k. Dividing into 256 parts instead of 2 at each step changes the constant, but not the asymptotic big O. You could do the same with quicksort (at each step choose 255 random pivots and use them to define 256 buckets of sublists). That changes the average runtime from n log_2 n to n log_256 n, but the only difference is a constant factor.
Note that I made this dumb error in three places (two obvious, one more subtle, I'll leave it to the interested reader to see where).
But my overall critique of his analysis of radix sort is, I believe, unaffected.
Oh no, I've never used it. I must not be a decent programmer. Downvote downvote downvote. Don't let anyone know.