On the other hand, quicksort scans memory in-order. Random access to memory is much, much worse than bad branch prediction. Using a heap in merge sort, for example, screws with both branch prediction and memory access.
For sorting, if you're minimizing the number of comparisons, the result of each compare should be random and independent of all others. So the only way to have "good" branch prediction when sorting an array of random numbers is to do lots of extra, superfluous compares, e.g. using an O(n^2) algorithm instead of an O(n log n) one.
The base case for std::sort in glibc is insertion sort. It's used for less than 6 elements. Nice and linear memory access patterns.
For sorting, if you're minimizing the number of comparisons, the result of each compare should be random and independent of all others. So the only way to have "good" branch prediction when sorting an array of random numbers is to do lots of extra, superfluous compares, e.g. using an O(n^2) algorithm instead of an O(n log n) one.
The base case for std::sort in glibc is insertion sort. It's used for less than 6 elements. Nice and linear memory access patterns.
Martin