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