• 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).