Gelling, William Cawley, Nebel, Markus E, Smith, Benjamin and Wild, Sebastian 
ORCID: 0000-0002-6061-9177
(2022)
Multiway Powersort.
[Preprint]
|
PDF
2209.06909v2.pdf - Other Download (997kB) | Preview |
Abstract
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 https://github.com/sebawild/powersort; 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: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3177011 |
Dimensions
Dimensions
