• 1 Introduction
  • 2 Preliminaries
    • 2.1 Notation
    • 2.2 Reference Version of Fat-Pivot Quicksort
    • 2.3 Quicksort and Search Trees
    • 2.4 Fringe-Balanced Trees
    • 2.5 Tail Bounds
    • 2.6 Logarithmic Tree Height w. h. p.
    • 2.7 Properties of the Entropy Function
  • 3 Input Models
    • 3.1 Multiset Model
    • 3.2 I. I. D. Model
    • 3.3 Relation of the Two Models
  • 4 Previous Work
    • 4.1 Multiset Sorting
    • 4.2 Quicksort on Multiset Permutations
    • 4.3 Fringe-Balanced Trees
  • 5 New Results
  • 6 Quicksort and Search Trees with Duplicates
    • 6.1 Recursion Trees
    • 6.2 Search Costs
  • 7 Saturated Fringe-Balanced Trees
    • 7.1 Stochastic Description
    • 7.2 Search Costs
  • 8 Quicksort With Many Duplicates
  • 9 Expected Search Costs in Saturated Trees
  • 10 Lower Bound For I. I. D. Sorting
  • 11 Proof of Main Result
  • 12 Conclusion
  • Appendix
    • A Index of Notation
      • A.1 Generic Mathematical Notation
      • A.2 Stochastics-related Notation
      • A.3 Notation for the Algorithm
      • A.4 Notation for the Analysis
    • B Height of Recursion Trees
    • Bibliography