Dual-pivot and beyond: The potential of multiway partitioning in quicksort

Wild, Sebastian ORCID: 0000-0002-6061-9177
(2018) Dual-pivot and beyond: The potential of multiway partitioning in quicksort. IT-INFORMATION TECHNOLOGY, 60 (3). pp. 173-177.

[img] Text
[it - Information Technology] Dual-pivot and beyond The potential of multiway partitioning in quicksort.pdf - Author Accepted Manuscript

Download (308kB) | Preview


<jats:title>Abstract</jats:title> <jats:p>Since 2011 the Java runtime library uses a Quicksort variant with two pivot elements. For reasons that remained unclear for years it is faster than the previous Quicksort implementation by more than 10 %; this is not only surprising because the previous code was highly-tuned and is used in many programming libraries, but also since earlier theoretical investigations suggested that using several pivots in Quicksort is not helpful.</jats:p> <jats:p>In my dissertation I proved by a comprehensive mathematical analysis of all sensible Quicksort partitioning variants that (a) indeed there is hardly any advantage to be gained from multiway partitioning in terms of the number of comparisons (and more generally in terms of CPU costs), but (b) multiway partitioning does significantly reduce the amount of data to be moved between CPU and main memory. Moreover, this more efficient use of the memory hierarchy is not achieved by any of the other well-known optimizations of Quicksort, but only through the use of several pivots.</jats:p>

Item Type: Article
Uncontrolled Keywords: Quicksort, multiway partitioning, average-case analysis, cache misses, external-memory model
Depositing User: Symplectic Admin
Date Deposited: 22 Oct 2019 14:21
Last Modified: 19 Jan 2023 00:21
DOI: 10.1515/itit-2018-0012
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3058989