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