BlockQuicksort: How Branch Mispredictions don't affect Quicksort

Stefan Edelkamp, Armin Weiß

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 es…