• 1 Introduction
    • 1.1 Related work
    • 1.2 Contributions
  • 2 QuickXsort
    • 2.1 QuickMergesort
    • 2.2 QuickHeapsort
  • 3 Preliminaries
    • 3.1 Notation
    • 3.2 Average costs of Mergesort
    • 3.3 Variance in Mergesort
  • 4 Transfer theorems for QuickXsort
    • 4.1 Prerequisites
    • 4.2 Growing sample sizes
    • 4.3 Fixed sample sizes
    • 4.4 Variance
  • 5 Analysis of QuickMergesort and QuickHeapsort
    • 5.1 Expected costs of QuickMergesort
    • 5.2 Variance in QuickMergesort
    • 5.3 QuickHeapsort
  • 6 QuickMergesort with base cases
    • 6.1 Insertionsort
    • 6.2 MergeInsertion
    • 6.3 Combination of (1,2)-Insertion and MergeInsertion
  • 7 Experiments
    • 7.1 Comparison counts
    • 7.2 Running time experiments
  • 8 Conclusion
  • 9 Full Proofs
    • 9.1 Preliminaries
    • 9.2 The QuickXsort recurrence
    • 9.3 Transfer theorem for growing sample sizes
    • 9.4 Large deviation and worst-case bounds
    • 9.5 Transfer theorem for fixed sample sizes
    • 9.6 Transfer theorem for the variance
    • 9.7 Base cases for QuickMergesort
  • References
  • A Notation
    • A.1 Generic mathematics
    • A.2 Stochastics-related notation
    • A.3 Specific notation for algorithms and analysis
  • B Mathematical Preliminaries
    • B.1 Hölder continuity
    • B.2 Chernoff bound
    • B.3 Continuous Master Theorem
  • C Pseudocode
    • C.1 Simple merge by swaps
    • C.2 Ping-pong Mergesort
    • C.3 Reinhardt's merge