Gelling, WC, Nebel, ME, Smith, B and Wild, S 
ORCID: 0000-0002-6061-9177
(2023)
Multiway Powersort.
In: Algorithm Engineering and Experiments (ALENEX23), 2023-1-22 - 2023-1-23, Florence.
|
PDF
main.pdf - Author Accepted Manuscript Download (783kB) | 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üller&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: | Conference or Workshop Item (Unspecified) |
|---|---|
| Depositing User: | Symplectic Admin |
| Date Deposited: | 28 Nov 2022 10:13 |
| Last Modified: | 01 Apr 2023 23:30 |
| Open Access URL: | https://arxiv.org/abs/2209.06909 |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3166400 |
Altmetric
Altmetric
