• 1 Introduction
    • 1.1 Adaptive Sorting
    • 1.2 Lower bound
    • 1.3 Results on Timsort and stack-based mergesort
  • 2 Preliminaries
    • 2.1 Nearly-Optimal Binary Search Trees
    • 2.2 Merge Costs
    • 2.3 Merge Trees
  • 3 Nearly-Optimal Merging Orders
    • 3.1 Peeksort: A Simple Top-Down Method
    • 3.2 Powersort: A Cache-Friendly Stack-Based Method
  • 4 Running-Time Study
    • 4.1 Setup
    • 4.2 Overhead of Nearly-Optimal Merge Order
    • 4.3 Practical speedups by adaptivity
    • 4.4 Non-optimality of Timsort
  • 5 Conclusion
    • 5.1 Extensions and future work
  • References