  Since the work of Kaligosi and Sanders (2006), it is well-known that
Quicksort -- which is commonly considered as one of the fastest in-place
sorting algorithms -- suffers in an essential way from branch mispredictions.
We present a novel approach to address this problem by partially decoupling
control from data flow: in order to perform the partitioning, we split the
input in blocks of constant size (we propose 128 data elements); then, all
elements in one block are compared with the pivot and the outcomes of the
comparisons are stored in a buffer. In a second pass, the respective elements
are rearranged. By doing so, we avoid conditional branches based on outcomes of
comparisons at all (except for the final Insertionsort). Moreover, we prove
that for a static branch predictor the average total number of branch
mispredictions is at most $\epsilon n \log n + O(n)$ for some small $\epsilon$
depending on the block size when sorting $n$ elements.
  Our experimental results are promising: when sorting random integer data, we
achieve an increase in speed of 80% over the GCC implementation of C++
std::sort. Also for many other types of data and non-random inputs, there is
still a significant speedup over std::sort. Only in few special cases like
sorted or almost sorted inputs, std::sort can beat out implementation.
Moreover, even on random input permutations, our implementation is even
slightly faster than an implementation of the highly tuned Super Scalar Sample
Sort, which uses a linear amount of additional space.
