Average case analysis of Java 7's dual pivot quicksort

DOI10.1007/978-3-642-33090-2_71MaRDI QIDQ2912899zbMATH OpenOpenAlexFDO

Authors Sebastian Wild, Markus E. Nebel

Publication date 25 September 2012

Published in Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.7409

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms (68W40)

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.9nlnn-2.46n+mathcalO(lnn)$ key comparisons and $0.6nlnn+0.08n+mathcalO(lnn)$ swaps.

Recommendations

• Average case and distributional analysis of dual-pivot quicksort
• Optimal Partitioning for Dual Pivot Quicksort
• Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme
• Optimal partitioning for dual-pivot quicksort
• DUAL PIVOT QUICKSORT

Cited in

(7)

• Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm
• Pivot sampling in dual-pivot quicksort: exploiting asymmetries in Yaroslavskiy's partitioning scheme
• Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme
• BlockQuicksort: avoiding branch mispredictions in Quicksort
• Average case and distributional analysis of dual-pivot quicksort
• Dual-pivot quicksort: optimality, analysis and zeros of associated lattice paths
• Dual-pivot quicksort: two-pivot partitioning with three-way partitions (Java 7 baseline)

This page was built for publication: Average case analysis of Java 7's dual pivot quicksort

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912899)