Improving Mergesort Performance by Optimizing Branch Prediction

By detecting arrays with a low degree of presort-edness, an adaptive mergesort algorithm can switch to a branch free implementation in order to reduce the runtime by up to 30% compared to traditional implementations and almost 50% compared to the mergesort based Timsort, while retaining the great performance of branch based variants on partially presorted arrays. By using a fast method of detecting the degree of presortedness, no prior knowledge about the array composition is required for the algorithm.