HOW MANY COMPARISONS DOES QUICKSORT USE

We examine the probability distribution of the number of comparisons n eeded by the Quicksort sorting algorithm, where probability arises due to the items being in random order. We develop a general class of dis tributions for the permutation of the items to be sorted which include s the uniform distribution on permutations as a special case. For this general class, the distribution of the number of comparisons is given by the solution of a simple recurrence relation. We provide an exact solution of the recurrence for very small n. We show that the solution can be approximated asymptotically by the solution of a ''quadratic'' operator equation. We exhibit three numerical solutions to the operat or equation for two different distributions on permutations from the g eneral class. We also exhibit numerical solutions for the case in whic h the algorithm is modified so that arrays are partitioned by the medi an-of-three selected items rather than by a single selected item. (C) 1995 Academic Press, Inc.