Is there an analysis of some other sorting algorithms and how the behave with branch prediction? I did some google searching and found one paper on merge sort and branch prediction.... specifically thinking about Mergesort, quicksort, heapsort, and introsort.
The paper linked to, and the tech report its based on, provide exactly that - an experimental analysis of sorting and branch predictors. Both are available at http://paulbiggar.com/research/#sorting.
Well, all the efficient comparison-based sorting algorithms (i.e. O(n log n) time) will cause Omega(n log n) mispredictions. So in a sense they're all the same*
At the same time, quicksort has the very nice property that if it accidentally picks a somewhat unbalanced pivot it naturally biases its branches making them easier to predict. This essentially cheapens the comparison branches it executes. I don't really know if that helps in practice though.
*Unless you jump through hoops/change the model of computation, one such way being conditional move instructions. There are more impractial ways too.
One good way is to use radix sort (it's generally faster for other reasons) and it never compares keys.
David Musser's (author of Introsort) paper "A Portable Cache Profiler Based on Source-Level Instrumentation"[1] looks at the cache behavior for Intro, Merge, and Heapsort in it's examples section. Not directly correlated, but possibly interesting nonetheless.
This stackoverflow post covers the "when to use" parts of various algorithms, I'm just wondering more about the practical vs theoretical runtimes of these sorts. http://stackoverflow.com/questions/1933759/when-is-each-sort...