Speaker: Jim Fill, Johns Hopkins University

Title: Probabilistic Analysis of QuickSort: An Overview

Abstract: We will begin by reviewing the operation of the randomized sorting algorithm QuickSort, invented by Tony Hoare in the early 1960s. We will then survey the probabilistic analysis of QuickSort, from the solution of a simple divide-and-conquer recurrence relation for the expected value of the number of key comparisons $K_n$ needed to sort $n$ distinct keys (items), to three techniques for establishing and characterizing a limit distribution for normalized $K_n$, to rates of convergence to the limit distribution, to a recent more realistic analysis that treats keys as symbol strings and measures the execution cost of QuickSort as the number of symbol comparisons.

Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
http://math.gmu.edu/
Tel. 703-993-1460, Fax. 703-993-1491