Why Is Dual-Pivot Quicksort Fast?


Wild, Sebastian ORCID: 0000-0002-6061-9177 (2015) Why Is Dual-Pivot Quicksort Fast? .

[thumbnail of 1511.01138v2.pdf] Text
1511.01138v2.pdf - Submitted version
Download (80kB) | Preview

Abstract

I discuss the new dual-pivot Quicksort that is nowadays used to sort arrays of primitive types in Java. I sketch theoretical analyses of this algorithm that offer a possible, and in my opinion plausible, explanation why (a) dual-pivot Quicksort is faster than the previously used (classic) Quicksort and (b) why this improvement was not already found much earlier.

Item Type: Other
Additional Information: extended abstract for Theorietage 2015 (https://www.uni-trier.de/index.php?id=55089) (v2 fixes a small bug in the pseudocode)
Uncontrolled Keywords: cs.DS, cs.DS
Depositing User: Symplectic Admin
Date Deposited: 15 Aug 2019 14:43
Last Modified: 19 Jan 2023 00:29
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3051859
Share
CORE (COnnecting REpositories)