One way to limit branching is to try to make applications of each operation as temporally contiguous as possible. That is, rather than take each data item and apply each operation to it, structure the operations so they can each be applied to the entire data set, one after the other. The branch predictor is happy because you're predictably looping over a simpler piece of code. The I-cache is happy because you're looping over a smaller piece of code.

Optimizing for the second level memory cache means making your data access patterns predictable (the above suggestion helps here, too) and keeping your data compact to get as much use out of each cache line as possible: Do you really need a 64-bit size_t to store an index into an array that will never be larger than a few thousand elements?

I split the code in two binaries: "code" (qsort) and "code2" (std::sort()) and then I ran both under a profiler (based on intel's performance counters).

It seams that qsort simply executes an order of magnitude more instructions for the same result than std::sort. On the other hand std::sort() code, even if it's faster, it has more branch miss-predictions.

Here [1] are the results if you want to have a look.

[1] https://gist.github.com/b97a6395c9a20c3d4cea

Limit branching: code like "a < b ? 1 : b < a ? -1 : 0" (yes, this is more or less my comparison function) is bad, because the CPU has to predict 2 comparisons, and CPU prediction os probably right at only ~50%. If prediction fails, then the queue of already "parsed" instructions gets flushed, and the CPUs processing unit has to wait for new instructions. Code which does not branch usually runs faster.

Therefore (a-b) would be a better comparison function, if you guarantee it does not overflow.

Loop unroll for limit branching. You can sort what's in cache, then load a new chunk of data into cached and sort it ... then merge the sorted chunks.