Average Case Analysis of Java 7's Dual Pivot Quicksort

Wild, Sebastian ORCID: 0000-0002-6061-9177 and Nebel, Markus E (2012) Average Case Analysis of Java 7's Dual Pivot Quicksort .

Text wild-nebel-2012.pdf - Author Accepted Manuscript Download (662kB) | Preview

Abstract

Recently, a new Quicksort variant due to Yaroslavskiy was chosen as standard sorting method for Oracle's Java 7 runtime library. The decision for the change was based on empirical studies showing that on average, the new algorithm is faster than the formerly used classic Quicksort. Surprisingly, the improvement was achieved by using a dual pivot approach, an idea that was considered not promising by several theoretical studies in the past. In this paper, we identify the reason for this unexpected success. Moreover, we present the first precise average case analysis of the new algorithm showing e.g. that a random permutation of length n is sorted using 1.9n ln n - 2.46n + O(ln n) key comparisons and 0.6n ln n + 0.08n + O(ln n) swaps. © 2012 Springer-Verlag.

Item Type:	Conference Item (Unspecified)
Additional Information:	Best paper award at ESA 2012, recorded talk: http://www.slideshare.net/sebawild/average-case-analysis-of-java-7s-dual-pivot-quicksort
Uncontrolled Keywords:	cs.DS, cs.DS, math.PR
Depositing User:	Symplectic Admin
Date Deposited:	21 Oct 2019 15:30
Last Modified:	22 May 2026 21:22
DOI:	10.1007/978-3-642-33090-2_71
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3058952
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.