A limit theorem for “quicksort”
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991) no. 1, pp. 85-100.
@article{ITA_1991__25_1_85_0,
author = {R\"osler, Uwe},
title = {A limit theorem for quicksort''},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {85--100},
publisher = {EDP-Sciences},
volume = {25},
number = {1},
year = {1991},
zbl = {0718.68026},
mrnumber = {1104413},
language = {en},
url = {www.numdam.org/item/ITA_1991__25_1_85_0/}
}
Rösler, Uwe. A limit theorem for “quicksort”. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991) no. 1, pp. 85-100. http://www.numdam.org/item/ITA_1991__25_1_85_0/

1. S. Cambanis, G. Simon and W. Stout, Inequalities for Ek (X, Y) when the Marginals are Fixed, Zeitschrift für Wahrscheinlichkeistheorie und verwandte Gebiete, 1976, 36, pp. 285-294. | MR 420778 | Zbl 0325.60002

2. M. Denker and U. Rösler, A Moment Estimate for Rank Statistics, Journal of Statistical Planning and Interference, 1985, 12, pp. 269-284. | MR 818380 | Zbl 0591.62033

3. L. Devroye, Exponential Bounds for the Running Time of a Selection Algorithm, Journal of Computer and System Sciences, 1985, 29, pp. 1-7. | MR 761047 | Zbl 0555.68018

4. N. Dunford and J. Schwartz, Linear Operators I, John Wiley & Sorts, 1963.

5. W. D. Frazer and A. C. Mckellar, Samplesort: A Sampling Approach to Minimal Storage Tree Sorting, Journal of the Association for Computing Machinery, 1970, 17, pp. 496-507. | MR 287744 | Zbl 0205.19202

6. P. Hennequin, Combinatorial Analysis of Quicksort Algorithm, Informatique théorique et Applications/Theoretical Informatics and Applications, 1989, 23, pp. 317-333. | Numdam | MR 1020477 | Zbl 0685.68058

7. C. A. R. Hoare, Algorithm 64: Quicksort, Communications of the Association for Computing Machinery, 1961, 4, p. 321.

8. C. A. R. Hoare, Quicksort, Computer Journal, 1962, 5, pp. 10-15. | MR 142216 | Zbl 0108.13601

9. D. E. Knuth, The art of computer programming, 3, Sorting and searching, M. A. Reading, Addison-Wesley, 1973. | MR 378456

10. R. Loeser, Some Performance Tests of "Quicksort" and Descendants, Communications of the Association for Computing Machinery 1974, 17, pp. 143-152.

11. P. Major, On the invariance principle for sums of independent identically distributed random variables, Journal of Multivariate Analysis, 1978, 8, pp. 487-517. | MR 520959 | Zbl 0408.60028

12. M. Régnier, A Limit Distribution for Quicksort, Informatique théorique et Applications/Theoretical Informatics and Applications, 1989, 23, pp. 335-343. | Numdam | MR 1020478 | Zbl 0677.68072

13. R. Sedgewick, The analysis of Quicksort programs, Acta Informatica, 1977, 7, pp. 327-355. | MR 451845 | Zbl 0325.68016

14. R. Sedgewick, Quicksort, Stanford Computer Science Report STAN-CS-75-492, Ph. d. thesis, 1975, Also published by Garland, Pub. Co., New York, 1980.

15. R. Sedgewick, Algorithms, Addison-Wesley, second edition, 1988. | Zbl 0717.68005