Pivot Sampling in Dual-Pivot Quicksort



Nebel, Markus E and Wild, Sebastian ORCID: 0000-0002-6061-9177
(2014) Pivot Sampling in Dual-Pivot Quicksort. .

[img] Text
nebel-wild-2014.pdf - Accepted Version

Download (894kB) | Preview

Abstract

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.

Item Type: Conference or Workshop Item (Unspecified)
Additional Information: presented at AofA 2014 (http://www.aofa14.upmc.fr/)
Uncontrolled Keywords: cs.DS, cs.DS, math.PR
Depositing User: Symplectic Admin
Date Deposited: 21 Oct 2019 14:07
Last Modified: 28 Apr 2022 21:12
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3058960