Partial Quicksort and weighted branching process

📙 Quicksort was chosen as one of the 10 most important algorithms. Quicksort serves also as a challenging random divide-and-conquer algorithm for a mathematical analysis. Starting with the worst case, the best case and the expected running time. In this book we look at two different models of sorting algorithms. Quicksort algorithm, sorts an unsorted array of n distinct elements. Partial Quicksort sorts the l smallest elements in a list of length n. We know nowadays much finer results on the limiting distribution, the existence via martingale methods and a characterization as a stochastic fixed point. The running time for many versions, actually all versions we know of, can be analyzed by the tools contraction method and Weighted Branching Process invented for Quicksort. Uwe Roesler pioneered the use of these techniques. A special hugs and kisses goes to my angel daughter “Malak” and both my sons, ”Ahmad” and "Yousof". Last but not least, I would like to thank my beloved wife, "Sara". I love you and look forward to spend the rest of my life with you. I dedicate this book to you.