{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T08:18:49Z","timestamp":1771661929024,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,8,8]],"date-time":"2015-08-08T00:00:00Z","timestamp":1438992000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds)","award":["COMMAS ref. TIN2013-46181-C2-1-R"],"award-info":[{"award-number":["COMMAS ref. TIN2013-46181-C2-1-R"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,8]]},"DOI":"10.1007\/s00453-015-0041-7","type":"journal-article","created":{"date-parts":[[2015,8,7]],"date-time":"2015-08-07T17:48:28Z","timestamp":1438969708000},"page":"632-683","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Analysis of Pivot Sampling in Dual-Pivot Quicksort: A Holistic Analysis of Yaroslavskiy\u2019s Partitioning Scheme"],"prefix":"10.1007","volume":"75","author":[{"given":"Markus E.","family":"Nebel","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Wild","sequence":"additional","affiliation":[]},{"given":"Conrado","family":"Mart\u00ednez","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,8]]},"reference":[{"key":"41_CR1","doi-asserted-by":"crossref","unstructured":"Aum\u00fcller, 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\u201344. Springer, LNCS, vol 7965 (2013)","DOI":"10.1007\/978-3-642-39206-1_4"},{"issue":"11","key":"41_CR2","doi-asserted-by":"crossref","first-page":"1249","DOI":"10.1002\/spe.4380231105","volume":"23","author":"JL Bentley","year":"1993","unstructured":"Bentley, J.L., McIlroy, M.D.: Engineering a sort function. Softw. Pract. Exp. 23(11), 1249\u20131265 (1993)","journal-title":"Softw. Pract. Exp."},{"issue":"1","key":"41_CR3","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0196-6774(02)00208-0","volume":"44","author":"HH Chern","year":"2002","unstructured":"Chern, H.H., Hwang, H.K., Tsai, T.H.: An asymptotic theory for cauchy-euler differential equations with applications to the analysis of algorithms. J. Algorithms 44(1), 177\u2013225 (2002)","journal-title":"J. Algorithms"},{"key":"41_CR4","volume-title":"A Course in Probability Theory","author":"KL Chung","year":"2001","unstructured":"Chung, K.L.: A Course in Probability Theory, 3rd edn. Academic Press, Waltham (2001)","edition":"3"},{"key":"41_CR5","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"41_CR6","doi-asserted-by":"crossref","DOI":"10.1002\/0471722162","volume-title":"Order Statistics","author":"HA David","year":"2003","unstructured":"David, H.A., Nagaraja, H.N.: Order Statistics, 3rd edn. Wiley-Interscience, New York (2003)","edition":"3"},{"issue":"2","key":"41_CR7","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/S0020-0190(02)00351-4","volume":"85","author":"M Durand","year":"2003","unstructured":"Durand, M.: Asymptotic analysis of an optimized quicksort algorithm. Inform. Process. Lett. 85(2), 73\u201377 (2003)","journal-title":"Inform. Process. Lett."},{"issue":"4","key":"41_CR8","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1145\/146370.146381","volume":"24","author":"V Estivill-Castro","year":"1992","unstructured":"Estivill-Castro, V., Wood, D.: A survey of adaptive sorting algorithms. ACM Comput. Surv. 24(4), 441\u2013476 (1992)","journal-title":"ACM Comput. Surv."},{"key":"41_CR9","first-page":"1","volume":"17","author":"J Fill","year":"2012","unstructured":"Fill, J., Janson, S.: The number of bit comparisons used by quicksort: an average-case analysis. Elect. J. Prob. 17, 1\u201322 (2012)","journal-title":"Elect. J. Prob."},{"key":"41_CR10","volume-title":"Concrete Mathematics: A Foundation for Computer Science","author":"RL Graham","year":"1994","unstructured":"Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, Boston (1994)"},{"key":"41_CR11","unstructured":"Hennequin, P.: Analyse en moyenne d\u2019algorithmes : tri rapide et arbres de recherche. PhD Thesis, Ecole Politechnique, Palaiseau (1991)"},{"key":"41_CR12","volume-title":"Computer Architecture: A Quantitative Approach","author":"JL Hennessy","year":"2006","unstructured":"Hennessy, J.L., Patterson, D.A.: Computer Architecture: A Quantitative Approach, 4th edn. Morgan Kaufmann Publishers, Burlington (2006)","edition":"4"},{"issue":"7","key":"41_CR13","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"CAR Hoare","year":"1961","unstructured":"Hoare, C.A.R.: Algorithm 65: Find. Commun. ACM 4(7), 321\u2013322 (1961)","journal-title":"Commun. ACM"},{"key":"41_CR14","doi-asserted-by":"crossref","unstructured":"Kaligosi, K., Sanders, P.: How branch mispredictions affect quicksort. In: Erlebach, T., Azar, Y. (ed.) European Symposium on Algorithms, pp. 780\u2013791. Springer, LNCS, vol 4168, (2006)","DOI":"10.1007\/11841036_69"},{"key":"41_CR15","doi-asserted-by":"crossref","unstructured":"Kushagra, S., L\u00f3pez-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\u201360. SIAM (2014)","DOI":"10.1137\/1.9781611973198.6"},{"issue":"1","key":"41_CR16","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1006\/jagm.1998.0985","volume":"31","author":"A LaMarca","year":"1999","unstructured":"LaMarca, A., Ladner, R.E.: The influence of caches on the performance of sorting. J. Algorithms 31(1), 66\u2013104 (1999)","journal-title":"J. Algorithms"},{"key":"41_CR17","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032886","volume-title":"Sorting: A Distribution Theory","author":"HM Mahmoud","year":"2000","unstructured":"Mahmoud, H.M.: Sorting: A Distribution Theory. Wiley, New York (2000)"},{"issue":"3","key":"41_CR18","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1137\/S0097539700382108","volume":"31","author":"C Mart\u00ednez","year":"2001","unstructured":"Mart\u00ednez, C., Roura, S.: Optimal sampling strategies in quicksort and quickselect. SIAM J. Comput. 31(3), 683\u2013705 (2001)","journal-title":"SIAM J. Comput."},{"key":"41_CR19","first-page":"114","volume-title":"Meeting on Analytic Algorithmics and Combinatorics","author":"C Mart\u00ednez","year":"2014","unstructured":"Mart\u00ednez, C., Nebel, M.E., Wild, S.: Analysis of branch misses in quicksort. In: Sedgewick, R., Ward, M.D. (eds.) Meeting on Analytic Algorithmics and Combinatorics, pp. 114\u2013128. SIAM, Philadelphia (2014)"},{"issue":"8","key":"41_CR20","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1002\/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#","volume":"27","author":"DR Musser","year":"1997","unstructured":"Musser, D.R.: Introspective sorting and selection algorithms. Softw. Pract. Exp. 27(8), 983\u2013993 (1997)","journal-title":"Softw. Pract. Exp."},{"key":"41_CR21","unstructured":"Nebel, M.E., Wild, S.: Pivot sampling in dual-pivot quicksort. In: Bousquet-M\u00e9lou, 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\u2013338 (2014)"},{"issue":"3\u20134","key":"41_CR22","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1002\/rsa.10010","volume":"19","author":"R Neininger","year":"2001","unstructured":"Neininger, R.: On a multivariate contraction method for random recursive structures with applications to quicksort. Random Struct. Algorithms 19(3\u20134), 498\u2013524 (2001)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"41_CR23","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1145\/375827.375837","volume":"48","author":"S Roura","year":"2001","unstructured":"Roura, S.: Improved master theorems for divide-and-conquer recurrences. J. ACM 48(2), 170\u2013205 (2001)","journal-title":"J. ACM"},{"key":"41_CR24","unstructured":"Sedgewick, R.: Quicksort. PhD Thesis, Stanford University (1975)"},{"issue":"4","key":"41_CR25","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/BF00289467","volume":"7","author":"R Sedgewick","year":"1977","unstructured":"Sedgewick, R.: The analysis of quicksort programs. Acta Inform. 7(4), 327\u2013355 (1977)","journal-title":"Acta Inform."},{"issue":"10","key":"41_CR26","doi-asserted-by":"crossref","first-page":"847","DOI":"10.1145\/359619.359631","volume":"21","author":"R Sedgewick","year":"1978","unstructured":"Sedgewick, R.: Implementing quicksort programs. Commun. ACM 21(10), 847\u2013857 (1978)","journal-title":"Commun. ACM"},{"key":"41_CR27","doi-asserted-by":"crossref","unstructured":"Vall\u00e9e, B., Cl\u00e9ment, 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\u2013763. Springer, LNCS, vol 5555, (2009)","DOI":"10.1007\/978-3-642-02927-1_62"},{"issue":"9","key":"41_CR28","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1145\/362736.362753","volume":"13","author":"MH Emden van","year":"1970","unstructured":"van Emden, M.H.: Increasing the efficiency of quicksort. Commun. ACM 13(9), 563\u2013567 (1970)","journal-title":"Commun. ACM"},{"key":"41_CR29","unstructured":"Wild, S.: Java 7\u2019s Dual-Pivot Quicksort. Master thesis, University of Kaiserslautern (2012)"},{"key":"41_CR30","doi-asserted-by":"crossref","unstructured":"Wild, S., Nebel, M.E.: Average case analysis of Java 7\u2019s dual pivot quicksort. In: Epstein, L., Ferragina, P. (ed.) European Symposium on Algorithms, pp. 825\u2013836. Springer, LNCS, vol 7501, (2012)","DOI":"10.1007\/978-3-642-33090-2_71"},{"key":"41_CR31","first-page":"55","volume-title":"Meeting on Algorithm Engineering and Experiments","author":"S Wild","year":"2013","unstructured":"Wild, S., Nebel, M.E., Reitzig, R., Laube, U.: Engineering Java 7\u2019s dual pivot quicksort using MaLiJAn. In: Sanders, P., Zeh, N. (eds.) Meeting on Algorithm Engineering and Experiments, pp. 55\u201369. SIAM, Philadelphia (2013)"},{"key":"41_CR32","doi-asserted-by":"crossref","unstructured":"Wild, S., Nebel, M.E., Mahmoud, H.: Analysis of quickselect under Yaroslavskiy\u2019s dual-pivoting algorithm. Algorithmica (to appear) (2014). doi: 10.1007\/s00453-014-9953-x","DOI":"10.1007\/s00453-014-9953-x"},{"issue":"3","key":"41_CR33","doi-asserted-by":"crossref","first-page":"22:1","DOI":"10.1145\/2629340","volume":"11","author":"S Wild","year":"2015","unstructured":"Wild, S., Nebel, M.E., Neininger, R.: Average case and distributional analysis of Java 7\u2019s dual pivot quicksort. ACM Trans. Algorithms 11(3), 22:1\u201322:42 (2015)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0041-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0041-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0041-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,29]],"date-time":"2019-08-29T04:47:17Z","timestamp":1567054037000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0041-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,8]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["41"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0041-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,8]]}}}