Average Case and Distributional Analysis of Java 7's Dual Pivot Quicksort
Sebastian Wild, Markus E. Nebel, Ralph Neininger · 2013
In 2009, Oracle replaced the long-serving sorting algorithm in its Java 7 runtime library by a new dual pivot Quicksort variant due to Yaroslavskiy. The decision was based on the strikingly good performance of Yaroslavskiy’s implementation in running time experiments. At that time, no precise investigations of the algorithm were available to explain its superior performance — on the contrary: Previous theoretical studies of other dual pivot Quicksort variants even discouraged the use two pivots. Only in 2012, two of the authors gave an average case analysis of a simplified version of Yaroslavskiy’s algorithm, proving that savings in the number of comparisons are possible. However, Yaroslavskiy’s algorithm needs more swaps, which renders the analysis inconclusive. To force the issue, we herein extend our analysis to the fully detailed style of Knuth: We determine the exact number of executed Java Bytecode instructions. Surprisingly, Yaroslavskiy’s algorithm needs sightly more Bytecode instructions than a simple implementation of classic Quicksort — despite contradicting running times. Like in Oracle’s library implementation we incorporate the use of Insertionsort on small subarrays and show that it indeed speeds up Yaroslavskiy’s Quicksort in terms of Bytecodes. Even if using optimal Insertionsort thresholds the new Quicksort variant again needs slightly more Bytecode instructions on average. Finally, we show that the (suitably normalized) costs of Yaroslavskiy’s algorithm converge to a random variable whose distribution is characterized by a fix point equation. From that, we compute variances of costs and show that for large n, costs are concentrated about their mean. 1.