I'm not sure you're quite right about 1. Depending on what you mean exactly. For example, insertion sort is O(n^2) but mispredicts O(n) times. That doesn't seem often to me.

There are (artificial) mergesorts that execute O(nlogn) branches but also mispredict O(n) times. See for example "branch mispredictions don't affect mergesort:" http://www.cphstl.dk/Paper/Quicksort/sea12.pdf

In the case of 2. I agree, although compiler support still isn't great -- I think. For almost all cases (integers, floats, strings) radix sorting would be even better -- fewer instructions, no comparison branches.