2014/03/26 by Markus E. Nebel, Nebel, Markus E., Sebastian Wild +1 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Blind Source Separation Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Methods and Algorithms #Probability (math.PR) #cs.DS #math.PR
paper · pdf · doi:10.48550/arxiv.1403.6602
presented at AofA 2014 (http://www.aofa14.upmc.fr/)
openalex publication_date 2014/03/26 · arxiv created 2014/06/13 · arxiv updated 2014/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries in its behavior. They were shown to cause a basic variant of this algorithm to use less comparisons than classic single-pivot Quicksort implementations. In this paper, we extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample and give the precise leading term of the average number of comparisons, swaps and executed Java Bytecode instructions. It turns out that - unlike for classic Quicksort, where it is optimal to choose the pivot as median of the sample - the asymmetries in Yaroslavskiy's algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, the optimal skew heavily depends on the employed cost measure; most strikingly, abstract costs like the number of swaps and comparisons yield a very different result than counting Java Bytecode instructions, which can be assumed most closely related to actual running time.