A limiting distribution for quicksort. (English) Zbl 0677.68072

Summary: We establish the existence of limiting distribution for the number of comparisons performed by quicksort, ot, equivalently, for the external path length of a binary search tree. We assume a uniform distribution of the data and prove a convergence in distribution and in \(L^ p\), \(p\geq 1\). The proof is based on a martingale argument.


68P10 Searching and sorting
60G42 Martingales with discrete parameter
68P05 Data structures


Full Text: DOI EuDML


[1] F. BACCELLI and A. M. MAKOWSKY, Direct martingale arguments for stability : The M/G/1 case, Systems & Control Letters, Vol. 6, 1985, p. 181-186. Zbl0568.60091 MR801868 · Zbl 0568.60091 · doi:10.1016/0167-6911(85)90038-6
[2] W. FELLER, An Introduction to Probability Theory and its Applications, Vol. II, Wiley, 1957. Zbl0077.12201 MR88081 · Zbl 0077.12201
[3] P. HENNEQUIN, Combinatorial analysis of Quicksort Algorithm, RAIRO, Th. Informatics and Applications (to appear). Zbl0685.68058 MR1020477 · Zbl 0685.68058
[4] C. A. HOARE, Quicksort, Computer Journal, Vol. 5, N^\circ 1, 1962. Zbl0108.13601 MR142216 · Zbl 0108.13601 · doi:10.1093/comjnl/5.1.10
[5] D. KNUTH, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, Mass., 1973. MR445948 · Zbl 0302.68010
[6] G. LOUCHARD, Exact and Asymptotic Distributions in Digital and Binary Seach Trees, RAIRO, Th. Informatics and Applications (to appear). Zbl0643.68077 MR928772 · Zbl 0643.68077
[7] J. NEVEU, Discrete-Parameter Martingale, English Translation, North-Holland, Amsterdam, 1975. Zbl0345.60026 MR402915 · Zbl 0345.60026
[8] R. SEDGEWICK, The Analysis of Quicksort Programs, Acta Informatica, Vol. 7, 1977, pp. 327-355, and in Quicksort, Garland Pub. Co., New York, 1980. Zbl0325.68016 MR451845 · Zbl 0325.68016 · doi:10.1007/BF00289467
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.