When I was a Computer Science student (not all too long ago as my colleague Doug likes to remind me) I was taught that you couldn’t get better performance in your sorting algorithm than your run-of-the-mill Quicksort algorithm (assuming you’re using a dynamic pivot of course, or else, all your reverse sorted data [read: base] are belong to us).
So when I stumbled across an interesting white paper from the Journal of Experimental Algorithmics a couple of months ago I was happy to learn that it is possible to get better performance than Quicksort. The paper boasts speeds twice as fast as any other string sorting algorithm due to fewer cache misses, which at least merits a quick (no pun intended) read.
The algorithm utilizes the Trie data structure, something that has always been a matter of much mystery to me. You can read a little bit more about Tries (and F#) over here. Let me know what you think!
White Paper: Cache-Conscious Sorting of Large Sets of Strings with Dynamic Tries"