Uwe Rösler

Quicksort, the Weighted Branching Process and the Contraction Method


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.