In this report, together with an accompanying tar ball, we release the source code of the sorting programs discussed and experimented in the following papers:

1. Amr Elmasry, Jyrki Katajainen, and Max Stenmark, Branch mispredictions don’t affect mergesort, Proceedings of the 11th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 7276, Springer-Verlag (2012), 160-171
2. Amr Elmasry and Jyrki Katajainen, Lean programs, branch mispredictions, and sorting, Proceedings of the 6th International Conference on Fun with Algorithms, Lecture Notes in Computer Science 7288, Springer-Verlag (2012), 119-130

The key idea in the described sorting programs is to decouple element comparisons from conditional branches. Therefore, these programs will incur significantly fewer branch mispredictions than, for example, the C++ standard-library introsort (introspective median-of-three quicksort that switches to heapsort if the recursion depth gets too high).

The sorting programs given can be divided into three categories depending on how many branch mispredictions they incur during their execution.

Lean:

O(1) branch mispredictions incurred when the branch predictor used by the underlying hardware is static.

Moderately optimized:

O(n) branch mispredictions incurred under the same assumptions as above.

Unoptimized:

The number of branch mispredictions incurred is proportional to the number of element comparisons performed.

As shown in [2], all programs can be made lean. However, in practice, a moderately-optimized variant is often faster than a lean variant. This is also true for the variants of heapsort, mergesort, and quicksort studied here.

@report{Kat2014S,
  author = {Jyrki Katajainen},
  title = {Sorting programs executing fewer branches},
  type = {CPH STL report},
  number = {2014-1},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {2014},
  pagetotal = {51},
}