Increasing the Efficiency of Quicksort A method is presented for the analysis of various generalizations of quicksort. The average asymptotic number of comparisons needed is shown to be an log^2(n). A formula is derived expressing a in terms of the probability distribution of the "bound" of a partition. This formula assumes a particularly simple form for a generalization already considered by Hoare, namely, choice of the bound as median of a random sample. The main contribution of this paper is another generalization of quicksort, which uses a bounding interval instead of a single element as bound. This generalization turns out to be easy to implement in a computer program. A numerical approximation shows that a = 1.140 for this version of quicksort compared with 1.386 for the original. This implies a decrease in number of comparisons of 18 percent; actual tests showed about 15 percent saving in computing time. CACM September, 1970 van Emden, M. H. sorting, quicksort, information content, entropy, distribution of median 3.73 4.49 5.31 5.6 CA700908 JB February 10, 1978 10:15 AM 1175 4 1997 1919 4 1997 1969 4 1997 1997 4 1997 1997 4 1997 2191 4 1997 2216 4 1997 2388 4 1997 2679 4 1997 2679 4 1997 3054 4 1997 3054 4 1997 3121 4 1997 1969 5 1997 1997 5 1997 1997 5 1997 1997 5 1997 308 5 1997 2216 5 1997 2679 5 1997 3054 5 1997 864 6 1997 970 6 1997 1175 6 1997 1175 6 1997 1190 6 1997 1228 6 1997 1880 6 1997 1919 6 1997 1919 6 1997 1969 6 1997 1969 6 1997 1969 6 1997 1980 6 1997 1997 6 1997 1997 6 1997 1997 6 1997 307 6 1997 308 6 1997 308 6 1997 309 6 1997 2017 6 1997 2042 6 1997 2679 6 1997 3187 6 1997 507 6 1997 716 6 1997 776 6 1997 783 6 1997