##
Uwe Rösler

Quicksort, the Weighted Branching Process and the Contraction Method

### Résumé

We will use the sorting algorithm Quicksort as the main vehicle to introduce the structure
Weighted Branching Processes (WBP) and the Contraction Method. A WBP is basically a genealogical
tree, where every path carries a weight compatible with the path structure. The weight
of a mother is randomly transformed to the weight of children . Typical questions are for the
total weight in or up to $n$th generation and their asymptotic behavior. The contraction method
provides some tools for that.

The divide-and-conquer algorithm Quicksort has this branching structure, the weight is
the remaining running time for sorting. As a result we obtain the Quicksort distribution,
the limiting distribution of the running time characterized by a stochastic fixed point equation.