×

Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy’s partitioning scheme. (English) Zbl 1350.68086

Summary: The new dual-pivot Quicksort by Vladimir Yaroslavskiy – used in Oracle’s Java runtime library since version 7 – features intriguing asymmetries. They make a basic variant of this algorithm use less comparisons than classic single-pivot Quicksort. In this paper, we extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample. Surprisingly, dual-pivot Quicksort then needs more comparisons than a corresponding version of classic Quicksort, so it is clear that counting comparisons is not sufficient to explain the running time advantages observed for Yaroslavskiy’s algorithm in practice. Consequently, we take a more holistic approach and give also the precise leading term of the average number of swaps, the number of executed Java Bytecode instructions and the number of scanned elements, a new simple cost measure that approximates I/O costs in the memory hierarchy. We determine optimal order statistics for each of the cost measures. It turns out that the asymmetries in Yaroslavskiy’s algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, we finally have a convincing explanation for the success of Yaroslavskiy’s algorithm in practice: compared with corresponding versions of classic single-pivot Quicksort, dual-pivot Quicksort needs significantly less I/Os, both with and without pivot sampling.

MSC:

68P10 Searching and sorting
68W40 Analysis of algorithms

Software:

MaLiJAn; Quicksort; Find
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Aumüller, M., Dietzfelbinger, M.: Optimal partitioning for dual pivot quicksort. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (ed.) International Colloquium on Automata, Languages and Programming, pp. 33-44. Springer, LNCS, vol 7965 (2013)
[2] Bentley, JL; McIlroy, MD, Engineering a sort function, Softw. Pract. Exp., 23, 1249-1265, (1993)
[3] Chern, HH; Hwang, HK; Tsai, TH, An asymptotic theory for Cauchy-Euler differential equations with applications to the analysis of algorithms, J. Algorithms, 44, 177-225, (2002) · Zbl 1030.68114
[4] Chung, K.L.: A Course in Probability Theory, 3rd edn. Academic Press, Waltham (2001)
[5] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009) · Zbl 1187.68679
[6] David, H.A., Nagaraja, H.N.: Order Statistics, 3rd edn. Wiley-Interscience, New York (2003) · Zbl 1053.62060
[7] Durand, M, Asymptotic analysis of an optimized quicksort algorithm, Inform. Process. Lett., 85, 73-77, (2003) · Zbl 1042.68119
[8] Estivill-Castro, V; Wood, D, A survey of adaptive sorting algorithms, ACM Comput. Surv., 24, 441-476, (1992)
[9] Fill, J; Janson, S, The number of bit comparisons used by quicksort: an average-case analysis, Elect. J. Prob., 17, 1-22, (2012) · Zbl 1244.68090
[10] Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, Boston (1994) · Zbl 0836.00001
[11] Hennequin, P.: Analyse en moyenne d’algorithmes : tri rapide et arbres de recherche. PhD Thesis, Ecole Politechnique, Palaiseau (1991) · Zbl 1398.68119
[12] Hennessy, J.L., Patterson, D.A.: Computer Architecture: A Quantitative Approach, 4th edn. Morgan Kaufmann Publishers, Burlington (2006) · Zbl 0752.68014
[13] Hoare, CAR, Algorithm 65: find, Commun. ACM, 4, 321-322, (1961)
[14] Kaligosi, K., Sanders, P.: How branch mispredictions affect quicksort. In: Erlebach, T., Azar, Y. (ed.) European Symposium on Algorithms, pp. 780-791. Springer, LNCS, vol 4168, (2006) · Zbl 1131.68435
[15] Kushagra, S., López-Ortiz, A., Qiao, A., Munro, J.I.: Multi-pivot quicksort: Theory and experiments. In: McGeoch, C.C., Meyer, U. (ed.) Meeting on Algorithm Engineering and Experiments, pp. 47-60. SIAM (2014) · Zbl 1030.68114
[16] LaMarca, A; Ladner, RE, The influence of caches on the performance of sorting, J. Algorithms, 31, 66-104, (1999) · Zbl 0928.68035
[17] Mahmoud, H.M.: Sorting: A Distribution Theory. Wiley, New York (2000) · Zbl 0985.68015
[18] Martínez, C; Roura, S, Optimal sampling strategies in quicksort and quickselect, SIAM J. Comput., 31, 683-705, (2001) · Zbl 0996.68038
[19] Martínez, C; Nebel, ME; Wild, S; Sedgewick, R (ed.); Ward, MD (ed.), Analysis of branch misses in quicksort, 114-128, (2014), Philadelphia
[20] Musser, DR, Introspective sorting and selection algorithms, Softw. Pract. Exp., 27, 983-993, (1997)
[21] Nebel, M.E., Wild, S.: Pivot sampling in dual-pivot quicksort. In: Bousquet-Mélou, M., Soria, M. (ed.) International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, DMTCS-HAL Proceedings Series, vol BA, pp. 325-338 (2014) · Zbl 1331.68068
[22] Neininger, R, On a multivariate contraction method for random recursive structures with applications to quicksort, Random Struct. Algorithms, 19, 498-524, (2001) · Zbl 0990.68054
[23] Roura, S, Improved master theorems for divide-and-conquer recurrences, J. ACM, 48, 170-205, (2001) · Zbl 1190.68097
[24] Sedgewick, R.: Quicksort. PhD Thesis, Stanford University (1975)
[25] Sedgewick, R, The analysis of quicksort programs, Acta Inform., 7, 327-355, (1977) · Zbl 0325.68016
[26] Sedgewick, R, Implementing quicksort programs, Commun. ACM, 21, 847-857, (1978) · Zbl 0386.68058
[27] Vallée, B., Clément, J., Fill, J.A., Flajolet, P.: The number of symbol comparisons in quicksort and quickselect. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (ed.) International Colloquium on Automata, Languages and Programming, pp 750-763. Springer, LNCS, vol 5555, (2009) · Zbl 1248.68181
[28] Emden, MH, Increasing the efficiency of quicksort, Commun. ACM, 13, 563-567, (1970) · Zbl 0198.50703
[29] Wild, S.: Java 7’s Dual-Pivot Quicksort. Master thesis, University of Kaiserslautern (2012) · Zbl 1337.68083
[30] Wild, S., Nebel, M.E.: Average case analysis of Java 7’s dual pivot quicksort. In: Epstein, L., Ferragina, P. (ed.) European Symposium on Algorithms, pp. 825-836. Springer, LNCS, vol 7501, (2012) · Zbl 1337.68083
[31] Wild, S; Nebel, ME; Reitzig, R; Laube, U; Sanders, P (ed.); Zeh, N (ed.), Engineering Java 7’s dual pivot quicksort using malijan, 55-69, (2013), Philadelphia
[32] Wild, S., Nebel, M.E., Mahmoud, H.: Analysis of quickselect under Yaroslavskiy’s dual-pivoting algorithm. Algorithmica (to appear) (2014). doi:10.1007/s00453-014-9953-x · Zbl 1336.68052
[33] Wild, S; Nebel, ME; Neininger, R, Average case and distributional analysis of Java 7’s dual pivot quicksort, ACM Trans. Algorithms, 11, 22:1-22:42, (2015) · Zbl 1398.68119
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.