{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:43:33Z","timestamp":1764783813580,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,11,17]],"date-time":"2015-11-17T00:00:00Z","timestamp":1447718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,12]]},"abstract":"<jats:p>\n            <jats:italic>Dual-pivot quicksort<\/jats:italic>\n            refers to variants of classical quicksort where in the partitioning step two pivots are used to split the input into three segments. This can be done in different ways, giving rise to different algorithms. Recently, a dual-pivot algorithm due to Yaroslavskiy received much attention, because it replaced the well-engineered quicksort algorithm in Oracle\u2019s Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed this algorithm and showed that on average it uses 1.9\n            <jats:italic>n<\/jats:italic>\n            ln\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) comparisons to sort an input of size\n            <jats:italic>n<\/jats:italic>\n            , beating standard quicksort, which uses 2\n            <jats:italic>n<\/jats:italic>\n            ln\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) comparisons. We introduce a model that captures all dual-pivot algorithms, give a unified analysis, and identify new dual-pivot algorithms that minimize the average number of key comparisons among all possible algorithms up to a linear term. This minimum is 1.8\n            <jats:italic>n<\/jats:italic>\n            ln\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ). For the case that the pivots are chosen from a small sample, we include a comparison of dual-pivot quicksort and classical quicksort. Specifically, we show that dual-pivot quicksort benefits from a skewed choice of pivots. We experimentally evaluate our algorithms and compare them to Yaroslavskiy\u2019s algorithm and the recently described 3-pivot quicksort algorithm of Kushagra et al. (ALENEX 2014).\n          <\/jats:p>","DOI":"10.1145\/2743020","type":"journal-article","created":{"date-parts":[[2015,11,18]],"date-time":"2015-11-18T13:42:28Z","timestamp":1447854148000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Optimal Partitioning for Dual-Pivot Quicksort"],"prefix":"10.1145","volume":"12","author":[{"given":"Martin","family":"Aum\u00fcller","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Ilmenau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Dietzfelbinger","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Ilmenau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,11,17]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press.","edition":"3"},{"key":"e_1_2_1_2_1","volume-title":"Dubhashi and Alessandro Panconesi","author":"Devdatt","year":"2009","unstructured":"Devdatt P. Dubhashi and Alessandro Panconesi . 2009 . Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press . Devdatt P. Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth Donald E.","key":"e_1_2_1_5_1","unstructured":"Donald E. Knuth . 1973. The Art of Computer Programming, Volume III: Sorting and Searching . Addison-Wesley . Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley."},{"volume-title":"Proceedings of the 16th Meeting on Algorithms Engineering and Experiments (ALENEX\u201914)","author":"Kushagra Shrinu","key":"e_1_2_1_6_1","unstructured":"Shrinu Kushagra , Alejandro L\u00f3pez-Ortiz , Aurick Qiao , and J. Ian Munro . 2014. Multi-pivot quicksort: Theory and experiments . In Proceedings of the 16th Meeting on Algorithms Engineering and Experiments (ALENEX\u201914) . SIAM , 47--60. Shrinu Kushagra, Alejandro L\u00f3pez-Ortiz, Aurick Qiao, and J. Ian Munro. 2014. Multi-pivot quicksort: Theory and experiments. In Proceedings of the 16th Meeting on Algorithms Engineering and Experiments (ALENEX\u201914). SIAM, 47--60."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790216.2790227"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382108"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375837"},{"key":"e_1_2_1_10_1","unstructured":"Robert Sedgewick. 1975. Quicksort. Ph.D. Dissertation. Standford University.  Robert Sedgewick. 1975. Quicksort. Ph.D. Dissertation. Standford University."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206018"},{"volume-title":"An Introduction to the Analysis of Algorithms","author":"Sedgewick Robert","key":"e_1_2_1_12_1","unstructured":"Robert Sedgewick and Philippe Flajolet . 1996. An Introduction to the Analysis of Algorithms . Addison-Wesley-Longman . Robert Sedgewick and Philippe Flajolet. 1996. An Introduction to the Analysis of Algorithms. Addison-Wesley-Longman."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/362736.362753"},{"volume-title":"Java 7\u2019s Dual Pivot Quicksort. Master\u2019s thesis","author":"Wild Sebastian","key":"e_1_2_1_14_1","unstructured":"Sebastian Wild . 2013. Java 7\u2019s Dual Pivot Quicksort. Master\u2019s thesis . University of Kaiserslautern. Sebastian Wild. 2013. Java 7\u2019s Dual Pivot Quicksort. Master\u2019s thesis. University of Kaiserslautern."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_71"},{"key":"e_1_2_1_16_1","volume-title":"Analysis of pivot sampling in dual-pivot quicksort. CoRR abs\/1412.0193","author":"Wild Sebastian","year":"2014","unstructured":"Sebastian Wild , Markus E. Nebel , and Conrado Mart\u00ednez . 2014. Analysis of pivot sampling in dual-pivot quicksort. CoRR abs\/1412.0193 ( 2014 ). Sebastian Wild, Markus E. Nebel, and Conrado Mart\u00ednez. 2014. Analysis of pivot sampling in dual-pivot quicksort. CoRR abs\/1412.0193 (2014)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629340"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790158.2790163"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2743020","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2743020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:15Z","timestamp":1750223235000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2743020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,17]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2,12]]}},"alternative-id":["10.1145\/2743020"],"URL":"https:\/\/doi.org\/10.1145\/2743020","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2015,11,17]]},"assertion":[{"value":"2014-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}