论文标题
Multiway Powersort
Multiway Powersort
论文作者
论文摘要
我们提出了一个稳定的Mergesort变体，Multiway Powersort，它利用了现有的运行，并找到了与k-way合并的订单几乎最佳的合并订单，而不是可以忽略不计的开销。这建立在Powersort（Munro＆Wild，ESA2018）的基础上，该公司最近在Python的Cpython参考实施中以及PYPY和PYPY和其他图书馆中取代了Timsort的次优合并政策。 Multiway Powersort减少了内存转移的数量，这越来越确定内部排序的成本（如Multiway QuickSort所观察到（Kushagra等人，Alenex，Alenex 2014;Aumüller＆Dietzfelbinger，Talg 2016; Talg 2016; talg 2016; Wild，PhD论文2016）以及Dual-PivotSort in jquicksort in j jquicksort in java runige in java runcruntime runtime。我们证明，我们的4向PowerSort实施可以在不损害PowerSort的最佳适应性绩效的情况下，超过标准（2-way）Powersort和其他稳定的分类方法实现实质性加速。
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.
