1 Introduction
1.1 Contributions.
1.2 Related Work.
2 Preliminaries
2.1 Lower Bound.
2.2 Merging and its memory-transfer cost.
2.3 Run-adaptive Mergesort.
3 Multiway Powersort
3.1 Intuition and Merge Tree.
3.2 k-way Powersort.
3.3 Analysis.
4 Results
4.1 Implementations and setup.
4.2 Experimental Setup.
4.3 Hypothesis 1: 4-way Powersort can yield significant performance improvements.
4.4 Hypothesis 2: Scanned elements explain the speedups.
4.5 Hypothesis 3: 4-way Powersort halves merge cost.
5 Conclusions
References
A C++ Code
A.1 4-way merge with sentinels.
A.2 3-way merge and 2-way merge.
A.3 4-way Powersort.
A.4 Sentinel-free 2-way merge.
A.5 Sentinel-free 4-way merge (merging by stages).