Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme

DOI10.1007/S00453-015-0041-7zbMATH Open1350.68086arXiv1412.0193OpenAlexW3122974231WikidataQ61734768 ScholiaQ61734768MaRDI QIDQ308946FDOQ308946

Authors: Markus E. Nebel, Sebastian Wild, Conrado Martínez 

Publication date: 6 September 2016

Published in: Algorithmica (Search for Journal in Brave)

Abstract: The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries. They make a basic variant of this algorithm use less comparisons than classic single-pivot Quicksort. In this paper, we extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample. Surprisingly, dual-pivot Quicksort then needs more comparisons than a corresponding version of classic Quicksort, so it is clear that counting comparisons is not sufficient to explain the running time advantages observed for Yaroslavskiy's algorithm in practice. Consequently, we take a more holistic approach and give also the precise leading term of the average number of swaps, the number of executed Java Bytecode instructions and the number of scanned elements, a new simple cost measure that approximates I/O costs in the memory hierarchy. We determine optimal order statistics for each of the cost measures. It turns out that the asymmetries in Yaroslavskiy's algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, we finally have a convincing explanation for the success of Yaroslavskiy's algorithm in practice: Compared with corresponding versions of classic single-pivot Quicksort, dual-pivot Quicksort needs significantly less I/Os, both with and without pivot sampling.

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

Recommendations

• Pivot sampling in dual-pivot quicksort: exploiting asymmetries in Yaroslavskiy's partitioning scheme
• Optimal partitioning for dual-pivot quicksort
• Average case and distributional analysis of dual-pivot quicksort
• Optimal Partitioning for Dual Pivot Quicksort
• Average case analysis of Java 7's dual pivot quicksort

zbMATH Keywords

average-case analysisdual-pivotexternal-memory modelI/O operationsmedian of threeQuicksortYaroslavskiy's partitioning method

Mathematics Subject Classification ID

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

Cites Work

• Introduction to algorithms.
• The Influence of Caches on the Performance of Sorting
• Title not available (Why is that?)
• The analysis of Quicksort programs
• Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm
• On a multivariate contraction method for random recursive structures with applications to quicksort
• Optimal sampling strategies in Quicksort and Quickselect
• Average case analysis of Java 7's dual pivot quicksort
• Order Statistics
• Average case and distributional analysis of dual-pivot quicksort
• Optimal Partitioning for Dual Pivot Quicksort
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• Increasing the efficiency of quicksort
• Asymptotic analysis of an optimized quicksort algorithm.
• Pivot sampling in dual-pivot quicksort: exploiting asymmetries in Yaroslavskiy's partitioning scheme
• Improved master theorems for divide-and-conquer recurrences
• Title not available (Why is that?)
• Implementing Quicksort programs
• The number of bit comparisons used by quicksort: an average-case analysis
• Title not available (Why is that?)
• An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
• Analysis of Branch Misses in Quicksort
• Multi-pivot quicksort: theory and experiments
• How Branch Mispredictions Affect Quicksort

Cited In (9)

• Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm
• Optimal partitioning for dual-pivot quicksort
• Optimal Partitioning for Dual Pivot Quicksort
• Dual-pivot quicksort: optimality, analysis and zeros of associated lattice paths
• Average case analysis of Java 7's dual pivot quicksort
• Average case and distributional analysis of dual-pivot quicksort
• How good is multi-pivot quicksort?
• Multi-pivot quicksort: theory and experiments
• Pivot sampling in dual-pivot quicksort: exploiting asymmetries in Yaroslavskiy's partitioning scheme

Uses Software

• Quicksort
• Find
• MaLiJAn

This page was built for publication: Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme

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