How good is multi-pivot quicksort?

DOI10.1145/2963102MaRDI QIDQ4962642zbMATH OpenOpenAlexFDO

Authors Martin Aumüller, Martin Dietzfelbinger, Pascal Klaue

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

sortingmulti-pivot quicksort

Mathematics Subject Classification ID

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

Abstract: Multi-Pivot Quicksort refers to variants of classical quicksort where in the partitioning step $k$ pivots are used to split the input into $k+1$ segments. For many years, multi-pivot quicksort was regarded as impractical, but in 2009 a 2-pivot approach by Yaroslavskiy, Bentley, and Bloch was chosen as the standard sorting algorithm in Sun's Java 7. In 2014 at ALENEX, Kushagra et al. introduced an even faster algorithm that uses three pivots. This paper studies what possible advantages multi-pivot quicksort might offer in general. The contributions are as follows: Natural comparison-optimal algorithms for multi-pivot quicksort are devised and analyzed. The analysis shows that the benefits of using multiple pivots with respect to the average comparison count are marginal and these strategies are inferior to simpler strategies such as the well known median-of-$k$ approach. A substantial part of the partitioning cost is caused by rearranging elements. A rigorous analysis of an algorithm for rearranging elements in the partitioning step is carried out, observing mainly how often array cells are accessed during partitioning. The algorithm behaves best if 3 to 5 pivots are used. Experiments show that this translates into good cache behavior and is closest to predicting observed running times of multi-pivot quicksort algorithms. Finally, it is studied how choosing pivots from a sample affects sorting cost. The study is theoretical in the sense that although the findings motivate design recommendations for multipivot quicksort algorithms that lead to running time improvements over known algorithms in an experimental setting, these improvements are small.

Recommendations

• Multi-pivot quicksort: theory and experiments
• Optimal partitioning for 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
• Pivot sampling in dual-pivot quicksort: exploiting asymmetries in Yaroslavskiy's partitioning scheme

Cited in

(11)

• Dual-pivot quicksort: optimality, analysis and zeros of associated lattice paths
• Sesquickselect: one and a half pivots for cache-efficient selection
• Simple and fast BlockQuicksort using Lomuto's partitioning scheme
• How Branch Mispredictions Affect Quicksort
• Quicksort is optimal for many equal keys
• Improving multikey Quicksort for sorting strings with many equal elements
• BlockQuicksort: avoiding branch mispredictions in Quicksort
• Multi-pivot quicksort: theory and experiments
• The middle pivot element algorithm
• Manticore: a framework for efficient multiparty computation supporting real number and Boolean arithmetic
• How Many Comparisons Does Quicksort Use?

This page was built for publication: How good is multi-pivot quicksort?

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