Multiway Powersort

Gelling, William Cawley, Nebel, Markus E, Smith, Benjamin and Wild, Sebastian ORCID: 0000-0002-6061-9177
(2022) Multiway Powersort. [Preprint]

[thumbnail of 2209.06909v2.pdf] PDF
2209.06909v2.pdf - Other

Download (997kB) | Preview


We present a stable mergesort variant, Multiway Powersort, that exploits existing runs and finds nearly-optimal merging orders for k-way merges with negligible overhead. This builds on Powersort (Munro & Wild, ESA2018), which has recently replaced Timsort's suboptimal merge policy in the CPython reference implementation of Python, as well as in PyPy and further libraries. Multiway Powersort reduces the number of memory transfers, which increasingly determine the cost of internal sorting (as observed with Multiway Quicksort (Kushagra et al., ALENEX 2014; Aum\"uller & Dietzfelbinger, TALG 2016; Wild, PhD thesis 2016) and the inclusion of Dual-Pivot Quicksort in the Java runtime library). We demonstrate that our 4-way Powersort implementation can achieve substantial speedups over standard (2-way) Powersort and other stable sorting methods without compromising the optimally run-adaptive performance of Powersort.

Item Type: Preprint
Additional Information: 17 pages; accompanying source code at; v2 adds new figure and text changes. v2 is identical to the ALENEX 2023 version
Uncontrolled Keywords: cs.DS, cs.DS
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 27 Nov 2023 08:53
Last Modified: 15 Mar 2024 16:14
DOI: 10.48550/arxiv.2209.06909
Related URLs: