{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T12:42:01Z","timestamp":1774442521711,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,10,10]],"date-time":"2016-10-10T00:00:00Z","timestamp":1476057600000},"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":[[2017,1,31]]},"abstract":"<jats:p>\n            <jats:italic>Multi-Pivot Quicksort<\/jats:italic>\n            refers to variants of classical quicksort where in the partitioning step\n            <jats:italic>k<\/jats:italic>\n            pivots are used to split the input into\n            <jats:italic>k<\/jats:italic>\n            + 1 segments. For many years, multi-pivot quicksort was regarded as impractical, but in 2009 a two-pivot approach by Yaroslavskiy, Bentley, and Bloch was chosen as the standard sorting algorithm in Sun\u2019s Java 7. In 2014 at ALENEX, Kushagra et al. introduced an even faster algorithm that uses three pivots. This article studies what possible advantages multi-pivot quicksort might offer in general. The contributions are as follows: Natural comparison-optimal algorithms for multi-pivot quicksort are devised and analyzed. The analysis shows that the benefits of using multiple pivots with respect to the average comparison count are marginal and these strategies are inferior to simpler strategies such as the well-known median-of-\n            <jats:italic>k<\/jats:italic>\n            approach. A substantial part of the partitioning cost is caused by rearranging elements. A rigorous analysis of an algorithm for rearranging elements in the partitioning step is carried out, observing mainly how often array cells are accessed during partitioning. The algorithm behaves best if three to five pivots are used. Experiments show that this translates into good cache behavior and is closest to predicting observed running times of multi-pivot quicksort algorithms. Finally, it is studied how choosing pivots from a sample affects sorting cost. The study is theoretical in the sense that although the findings motivate design recommendations for multipivot quicksort algorithms that lead to running-time improvements over known algorithms in an experimental setting, these improvements are small.\n          <\/jats:p>","DOI":"10.1145\/2963102","type":"journal-article","created":{"date-parts":[[2016,10,11]],"date-time":"2016-10-11T18:01:35Z","timestamp":1476208895000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["How Good Is Multi-Pivot Quicksort?"],"prefix":"10.1145","volume":"13","author":[{"given":"Martin","family":"Aum\u00fcller","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Ilmenau"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Dietzfelbinger","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Ilmenau, Ilmenau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Klaue","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Ilmenau, Ilmenau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,10,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2743020"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA'16)","author":"Aum\u00fcller Martin","year":"2016","unstructured":"Martin Aum\u00fcller , Martin Dietzfelbinger , Clemens Heuberger , Daniel Krenn , and Helmut Prodinger . 2016 . Counting zeros in random walks on the integers and analysis of optimal dual-pivot quicksort. CoRR abs\/1602.04031 (2016) , In Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA'16) , 3. Martin Aum\u00fcller, Martin Dietzfelbinger, Clemens Heuberger, Daniel Krenn, and Helmut Prodinger. 2016. Counting zeros in random walks on the integers and analysis of optimal dual-pivot quicksort. CoRR abs\/1602.04031 (2016), In Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA'16), 3."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380231105"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997)","author":"Bentley Jon Louis","year":"1997","unstructured":"Jon Louis Bentley and Robert Sedgewick . 1997 . Fast algorithms for sorting and searching strings . In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997) . ACM, 360--369. Jon Louis Bentley and Robert Sedgewick. 1997. Fast algorithms for sorting and searching strings. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997). ACM, 360--369."},{"key":"e_1_2_1_7_1","unstructured":"Joshua Bloch. 2015. Personal Communication.  Joshua Bloch. 2015. Personal Communication."},{"key":"e_1_2_1_8_1","volume-title":"A Discipline of Programming","author":"Dijkstra Edsger W.","unstructured":"Edsger W. Dijkstra . 1976. A Discipline of Programming . Prentice-Hall . Edsger W. Dijkstra. 1976. A Discipline of Programming. Prentice-Hall."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA'16)","author":"Edelkamp Stefan","year":"2016","unstructured":"Stefan Edelkamp and Armin Weiss . 2016 . BlockQuicksort: Avoiding branch mispredictions in quicksort . In Proceedings of the 24th Annual European Symposium on Algorithms (ESA'16) . 38:1--38:16. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.ESA.2016.38 10.4230\/LIPIcs.ESA.2016.38 Stefan Edelkamp and Armin Weiss. 2016. BlockQuicksort: Avoiding branch mispredictions in quicksort. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA'16). 38:1--38:16. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.ESA.2016.38"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_15"},{"key":"e_1_2_1_12_1","unstructured":"Agner Fog. 2014. 4. Instruction tables. Retrieved from http:\/\/www.agner.org\/optimize\/instruction_tables.pdf.  Agner Fog. 2014. 4. Instruction tables. Retrieved from http:\/\/www.agner.org\/optimize\/instruction_tables.pdf."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/321592.321600"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206045"},{"key":"e_1_2_1_15_1","volume-title":"Concrete Mathematics\u2014A Foundation for Computer Science","author":"Graham Ronald L.","unstructured":"Ronald L. Graham , Donald E. Knuth , and Oren Patashnik . 1994. Concrete Mathematics\u2014A Foundation for Computer Science , 2 nd ed. Addison-Wesley . Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. 1994. Concrete Mathematics\u2014A Foundation for Computer Science, 2nd ed. Addison-Wesley.","edition":"2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0121057"},{"key":"e_1_2_1_19_1","unstructured":"Vasileios Iliopoulos. 2014. A note on multipivot quicksort. CoRR abs\/1407.7459.  Vasileios Iliopoulos. 2014. A note on multipivot quicksort. CoRR abs\/1407.7459."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_69"},{"key":"e_1_2_1_21_1","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth Donald E.","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."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790174.2790180"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0985"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2010.5470444"},{"key":"e_1_2_1_25_1","unstructured":"David Levinthal. 2009. Performance Analysis Guide for Intel Core i7 Processor and Intel Xeon 5500 processors. Retrieved from https:\/\/software.intel.com\/sites\/products\/collateral\/hpc\/vtune\/performance_analysis_guide.pdf.  David Levinthal. 2009. Performance Analysis Guide for Intel Core i7 Processor and Intel Xeon 5500 processors. Retrieved from https:\/\/software.intel.com\/sites\/products\/collateral\/hpc\/vtune\/performance_analysis_guide.pdf."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790216.2790227"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382108"},{"key":"e_1_2_1_28_1","first-page":"5","article-title":"Engineering radix sort","volume":"6","author":"McIlroy Peter M.","year":"1993","unstructured":"Peter M. McIlroy , Keith Bostic , and M. Douglas McIlroy . 1993 . Engineering radix sort . Comput. Syst. 6 , 1 (1993), 5 -- 27 . Peter M. McIlroy, Keith Bostic, and M. Douglas McIlroy. 1993. Engineering radix sort. Comput. Syst. 6, 1 (1993), 5--27.","journal-title":"Comput. Syst."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0041-7"},{"key":"e_1_2_1_30_1","volume-title":"Algorithms for Memory Hierarchies, Advanced Lectures {Dagstuhl Research Seminar, March 10--14","author":"Rahman Naila","year":"2002","unstructured":"Naila Rahman . 2002. Algorithms for hardware caches and TLB . In Algorithms for Memory Hierarchies, Advanced Lectures {Dagstuhl Research Seminar, March 10--14 , 2002 }. 171--192. Naila Rahman. 2002. Algorithms for hardware caches and TLB. In Algorithms for Memory Hierarchies, Advanced Lectures {Dagstuhl Research Seminar, March 10--14, 2002}. 171--192."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375837"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_69"},{"key":"e_1_2_1_33_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_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206018"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/362736.362753"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_71"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629340"},{"key":"e_1_2_1_39_1","unstructured":"Vladimir Yaroslavskiy. 2009. Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort (Thread). Retrieved from http:\/\/osdir.com\/ml\/java-openjdk-core-libs-devel\/2009-09\/msg00160.html.  Vladimir Yaroslavskiy. 2009. Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort (Thread). Retrieved from http:\/\/osdir.com\/ml\/java-openjdk-core-libs-devel\/2009-09\/msg00160.html."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2963102","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2963102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:04Z","timestamp":1750222444000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2963102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,10]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1,31]]}},"alternative-id":["10.1145\/2963102"],"URL":"https:\/\/doi.org\/10.1145\/2963102","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,10]]},"assertion":[{"value":"2015-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}