{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T13:55:37Z","timestamp":1773410137489,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,11,4]],"date-time":"2014-11-04T00:00:00Z","timestamp":1415059200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9953-x","type":"journal-article","created":{"date-parts":[[2014,11,3]],"date-time":"2014-11-03T15:51:35Z","timestamp":1415029895000},"page":"485-506","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Analysis of Quickselect Under Yaroslavskiy\u2019s Dual-Pivoting Algorithm"],"prefix":"10.1007","volume":"74","author":[{"given":"Sebastian","family":"Wild","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus E.","family":"Nebel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hosam","family":"Mahmoud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,4]]},"reference":[{"issue":"1","key":"9953_CR1","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","volume":"5","author":"CAR Hoare","year":"1962","unstructured":"Hoare, C.A.R.: Quicksort. Comput. J. 5(1), 10\u201316 (1962)","journal-title":"Comput. J."},{"issue":"7","key":"9953_CR2","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"},{"issue":"4","key":"9953_CR3","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."},{"key":"9953_CR4","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. (eds.) ESA 2012, LNCS, vol. 7501, pp. 825\u2013836. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-33090-2_71"},{"issue":"01","key":"9953_CR5","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1017\/S0963548397003325","volume":"7","author":"P Kirschenhofer","year":"1998","unstructured":"Kirschenhofer, P., Prodinger, H.: Comparisons in Hoare\u2019s Find algorithm. Comb. Probab. Comput. 7(01), 111\u2013120 (1998)","journal-title":"Comb. Probab. Comput."},{"key":"9953_CR6","volume-title":"The Art Of Computer Programming: Searching and Sorting","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art Of Computer Programming: Searching and Sorting, 2nd edn. Addison Wesley, Reading (1998)","edition":"2"},{"issue":"3","key":"9953_CR7","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1214\/12-AAP866","volume":"23","author":"JA Fill","year":"2013","unstructured":"Fill, J.A.: Distributional convergence for the number of symbol comparisons used by quicksort. Ann. Appl. Probab. 23(3), 1129\u20131147 (2013)","journal-title":"Ann. Appl. Probab."},{"key":"9953_CR8","doi-asserted-by":"crossref","first-page":"1763","DOI":"10.1016\/j.tcs.2010.01.029","volume":"411","author":"HM Mahmoud","year":"2010","unstructured":"Mahmoud, H.M.: Distributional analysis of swaps in quick select. Theor. Comput. Sci. 411, 1763\u20131769 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"21\u201323","key":"9953_CR9","doi-asserted-by":"crossref","first-page":"2279","DOI":"10.1016\/j.tcs.2009.01.006","volume":"410","author":"C Mart\u00ednez","year":"2009","unstructured":"Mart\u00ednez, C., Prodinger, H.: Moves and displacements of particular elements in quicksort. Theor. Comput. Sci. 410(21\u201323), 2279\u20132284 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9953_CR10","unstructured":"Wild, S., Nebel, M.E., Neininger, R.: Average case and distributional analysis of Java 7\u2019s dual pivot quicksort. ACM Trans. Algorithms (accepted for publication). http:\/\/arxiv.org\/abs\/1304.0988"},{"key":"9953_CR11","unstructured":"Hennequin, P.: Analyse en moyenne d\u2019algorithmes: tri rapide et arbres de recherche. PhD Thesis, Ecole Politechnique, Palaiseau (1991)"},{"key":"9953_CR12","unstructured":"Sedgewick, R.: Quicksort. PhD Thesis, Stanford University (1975)"},{"issue":"3","key":"9953_CR13","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1051\/ita\/1989230303171","volume":"23","author":"P Hennequin","year":"1989","unstructured":"Hennequin, P.: Combinatorial analysis of quicksort algorithm. Informatique th\u00e9orique et applications 23(3), 317\u2013333 (1989)","journal-title":"Informatique th\u00e9orique et applications"},{"issue":"4","key":"9953_CR14","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1145\/358027.381121","volume":"27","author":"J Bentley","year":"1984","unstructured":"Bentley, J.: Programming pearls: how to sort. Commun. ACM 27(4), 287\u2013291 (1984)","journal-title":"Commun. ACM"},{"key":"9953_CR15","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, New York (2001)","edition":"3"},{"key":"9953_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-33483-2","volume-title":"Modelling Extremal Events","author":"P Embrechts","year":"1997","unstructured":"Embrechts, P., Kl\u00fcppelberg, C., Mikosch, T.: Modelling Extremal Events. Springer, Berlin (1997)"},{"key":"9953_CR17","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1007\/s10959-008-0156-8","volume":"22","author":"G Alsmeyer","year":"2009","unstructured":"Alsmeyer, G., Iksanov, A., R\u00f6sler, U.: On distributional properties of perpetuities. J. Theor. Probab. 22, 666\u2013682 (2009)","journal-title":"J. Theor. Probab."},{"key":"9953_CR18","unstructured":"Wild, S.: Java 7\u2019s Dual Pivot Quicksort. Master thesis, University of Kaiserslautern (2012)"},{"issue":"4","key":"9953_CR19","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1051\/ita\/1995290402551","volume":"29","author":"HM Mahmoud","year":"1995","unstructured":"Mahmoud, H.M., Modarres, R., Smythe, R.T.: Analysis of quickselect: an algorithm for order statistics. Informatique th\u00e9orique et applications 29(4), 255\u2013276 (1995)","journal-title":"Informatique th\u00e9orique et applications"},{"issue":"4","key":"9953_CR20","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0167-7152(95)00139-5","volume":"28","author":"J Lent","year":"1996","unstructured":"Lent, J., Mahmoud, H.M.: Average-case analysis of multiple quickselect: an algorithm for finding order statistics. Stat. Probab. Lett. 28(4), 299\u2013310 (1996)","journal-title":"Stat. Probab. Lett."},{"issue":"3","key":"9953_CR21","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0020-0190(95)00150-B","volume":"56","author":"H Prodinger","year":"1995","unstructured":"Prodinger, H.: Multiple quickselect\u2014Hoare\u2019s Find algorithm for several elements. Inf. Process. Lett. 56(3), 123\u2013129 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"3\u20134","key":"9953_CR22","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<189::AID-RSA1>3.0.CO;2-R","volume":"13","author":"A Panholzer","year":"1998","unstructured":"Panholzer, A., Prodinger, H.: A generating functions approach for the analysis of grand averages for multiple QUICKSELECT. Random Struct. Algorithms 13(3\u20134), 189\u2013209 (1998)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"9953_CR23","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1051\/ita\/1991250100851","volume":"25","author":"U R\u00f6sler","year":"1991","unstructured":"R\u00f6sler, U.: A limit theorem for \u201cquicksort\u201d. Informatique th\u00e9orique et applications 25(1), 85\u2013100 (1991)","journal-title":"Informatique th\u00e9orique et applications"},{"issue":"3","key":"9953_CR24","doi-asserted-by":"crossref","first-page":"770","DOI":"10.2307\/1428133","volume":"27","author":"ST Rachev","year":"1995","unstructured":"Rachev, S.T., R\u00fcschendorf, L.: Probability metrics and recursive algorithms. Adv. Appl. Probab. 27(3), 770\u2013799 (1995)","journal-title":"Adv. Appl. Probab."},{"issue":"3\u20134","key":"9953_CR25","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":"1","key":"9953_CR26","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1214\/aoap\/1075828056","volume":"14","author":"R Neininger","year":"2004","unstructured":"Neininger, R., R\u00fcschendorf, L.: A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab. 14(1), 378\u2013418 (2004)","journal-title":"Ann. Appl. Probab."},{"issue":"1","key":"9953_CR27","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/BF02679621","volume":"29","author":"U R\u00f6sler","year":"2001","unstructured":"R\u00f6sler, U.: On the analysis of stochastic divide and conquer algorithms. Algorithmica 29(1), 238\u2013261 (2001)","journal-title":"Algorithmica"},{"issue":"1","key":"9953_CR28","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02679611","volume":"29","author":"U R\u00f6sler","year":"2001","unstructured":"R\u00f6sler, U., R\u00fcschendorf, L.: The contraction method for recursive algorithms. Algorithmica 29(1), 3\u201333 (2001)","journal-title":"Algorithmica"},{"issue":"1","key":"9953_CR29","doi-asserted-by":"crossref","first-page":"252","DOI":"10.2307\/1427920","volume":"28","author":"R Gr\u00fcbel","year":"1996","unstructured":"Gr\u00fcbel, R., R\u00f6sler, U.: Asymptotic distribution theory for Hoare\u2019s selection algorithm. Adv. Appl. Probab. 28(1), 252\u2013269 (1996)","journal-title":"Adv. Appl. Probab."},{"key":"9953_CR30","first-page":"271","volume":"3","author":"U R\u00f6sler","year":"2004","unstructured":"R\u00f6sler, U.: QUICKSELECT revisited. J. Iran. Stat. Inst. 3, 271\u2013296 (2004)","journal-title":"J. Iran. Stat. Inst."},{"issue":"1","key":"9953_CR31","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1239\/jap\/1032192549","volume":"35","author":"R Gr\u00fcbel","year":"1998","unstructured":"Gr\u00fcbel, R.: Hoare\u2019s selection algorithm: a Markov chain approach. J. Appl. Probab. 35(1), 36\u201345 (1998)","journal-title":"J. Appl. Probab."},{"key":"9953_CR32","doi-asserted-by":"crossref","unstructured":"Hwang, H.K., Tsai, T.H.: Quickselect and Dickman function. Comb. Probab. Comput. 11, 353\u2013371 (2000)","DOI":"10.1017\/S0963548302005138"},{"key":"9953_CR33","unstructured":"Aum\u00fcller, M., Dietzfelbinger, M.: Optimal partitioning for dual pivot quicksort (2013). http:\/\/arxiv.org\/abs\/1303.5217"},{"issue":"3","key":"9953_CR34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1798596.1798606","volume":"6","author":"C Mart\u00ednez","year":"2010","unstructured":"Mart\u00ednez, C., Panario, D., Viola, A.: Adaptive sampling strategies for quickselects. ACM Trans. Algorithms 6(3), 1\u201345 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"9953_CR35","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 (2001)","journal-title":"SIAM J. Comput."},{"key":"9953_CR36","doi-asserted-by":"crossref","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.) ALENEX 2013, pp. 55\u201369. SIAM (2013)","DOI":"10.1137\/1.9781611972931.5"},{"issue":"3","key":"9953_CR37","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1007\/s00453-009-9294-3","volume":"58","author":"JA Fill","year":"2009","unstructured":"Fill, J.A., Nakama, T.: Analysis of the expected number of bit comparisons required by quickselect. Algorithmica 58(3), 730\u2013769 (2009)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9953-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9953-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9953-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T20:04:37Z","timestamp":1565985877000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9953-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,4]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9953"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9953-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,4]]}}}