Improving Quicksort Performance by Optimizing Branch Prediction
Jonas Peeters, Jan Haase · 2022
By detecting arrays with a low degree of presort-edness, an adaptive quicksort algorithm can switch to a branch free implementation in order to reduce the runtime by up to 2.5 times compared to traditional implementations and outperform strictly branch free algorithms on arrays with a high degree of presortedness. By using a fast method of detecting the degree of presortedness, no prior knowledge about the array composition is required for the algorithm.