Analysis of Pivot Sampling in Dual-Pivot Quicksort: A Holistic Analysis of Yaroslavskiy's Partitioning Scheme
- Submitting institution
-
The University of Liverpool
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12177
- Type
- D - Journal article
- DOI
-
10.1007/s00453-015-0041-7
- Title of journal
- Algorithmica: an international journal in computer science
- Article number
- -
- First page
- 632
- Volume
- 75
- Issue
- 4
- ISSN
- 0178-4617
- Open access status
- Out of scope for open access requirements
- Month of publication
- August
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
-
- Citation count
- 5
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This is the full paper of "Pivot Sampling in Dual-Pivot Quicksort—Exploiting Asymmetries in Yaroslavskiy’s Partitioning Scheme" (AofA 2014). The results are a core part of Wild's dissertation, which won the "GI Dissertationspreis 2016" for the best dissertation in computer science in Germany, Austria, and Switzerland. The developed analysis techniques have been used extensively by other researchers, for example in "How good is multi-pivot quicksort?" (TALG 2016), "BlockQuicksort: Avoiding branch mispredictions in Quicksort" (J. Exp. Alg. 2019), and "Simple and Fast BlockQuicksort using Lomuto's Partitioning Scheme" (ALENEX 2019).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -