IntroSort & multi-threaded radix
I found a link in Charles Bloom’s rants, about “intro sort”. The author claims it is faster than STL’s version. Long story short: it is.
Once in a while I get doubts about how fast a radix sort is, compared to a vanilla STL sort, so I ran the good old tests again. Any news? Nope, radix is still faster in cases that interest me.
While I was at it, I quickly put together a “multithreaded radix sort” where half the list of items is sorted in a different thread, and then there’s an extra pass to merge the results. Result: faster than the single thread version on my dual core - at list for large amounts of elements to sort. Cool 
Below are the results when sorting various numbers of floats.
- Radix: single thread radix sort, 3 passes
- Radix MT: multi thread version
- IntroSort: sort whose source code was given in the link above
- std::sort: your vanilla STL sort
