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