There are two ways to avoid branch-mispredictions when sorting: 1. use comparison results in a non-branching manner (e.g. conditional load instructions) 2. use them in a branching manner, but where you can predict the branch direction most of the time (only wrong guesses count). Insertion sort can be viewed as using method #2 and achieves only O(N) mispredictions during sorting N items in order N^2 time. My way of programming heapsort using both methods achieves O(N) misprediction bound, while sorting in O(NlogN) time. What is the minimum possible #mispredictions? [Is O(N) actually already optimal?] The answer is zero! That is because the much-derided quadratic-time "bubble sort" algorithm involves only comparing adjacent elements (if larger, move right 1 hop). This can be done entirely with conditional loads; no branching based on the results of comparisons at all. Also, Batcher's "odd even merge" sorting network (aka "bitonic sort") also involves zero, it runs in O(N*(logN)^2) time. And the AKS sorting network, which is practically utterly useless due to huge constant factors, also achieves zero and sorts in O(NlogN) time. However, there are caveats attached to those results -- the loop-structure of bubble sort still involves branching (just not branching based on item-comparisons) and those branches involve order N mispredictions. Batcher involves at least order NlogN mispredictions of this kind too. I'm not sure how many AKS would involve, perhaps only order (logN)^2. This caveat could be removed by doing bubble sort in a single-loop manner where the two indices are derived algebraically from the one loop index. In that case there is only a single branch-misprediction in the whole process. And "one" is surely minimum possible since you have to detect "algorithm has ended" via a branch.