• 1 Introduction
  • 2 Previous Work
  • 3 Preliminaries
  • 4 QuickXsort
    • 4.1 Recurrence for Expected Costs
  • 5 The Transfer Theorem
  • 6 QuickMergesort
    • 6.1 Average Case of Mergesort
  • 7 Solving the Recurrence: Leading Term
    • 7.1 The Shape Function
    • 7.2 Computing the Toll Function
    • 7.3 Which Case of the CMT?
    • 7.4 Cancellations
  • 8 Solving the Recurrence: The Linear Term
    • 8.1 Error Bound
  • 9 Discussion
    • 9.1 QuickHeapsort
    • 9.2 QuickMergesort
    • 9.3 Future Work
  • A Notation
    • A.1 Generic Mathematics
    • A.2 Stochastics-related Notation
    • A.3 Notation for the Algorithm
  • B The Continuous Master Theorem
  • C Local Limit Law for the Beta-Binomial Distribution
  • D Smoothness of the Shape Function
  • E Approximation by (Incomplete) Beta Integrals
  • References