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

See for yourself. The source code is here.

Comments are closed. cialis