{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T23:36:46Z","timestamp":1780357006836,"version":"3.54.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T00:00:00Z","timestamp":1548806400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>\n            It is well known that Quicksort\u00a0-- which is commonly considered as one of the fastest in-place sorting algorithms -- suffers in an essential way from branch mispredictions. We present a novel approach to addressing this problem by partially decoupling control from dataflow: in order to perform the partitioning, we split the input into blocks of constant size. Then, all elements in one block are compared with the pivot and the outcomes of the comparisons are stored in a buffer. In a second pass, the respective elements are rearranged. By doing so, we avoid conditional branches based on outcomes of comparisons (except for the final Insertionsort). Moreover, we prove that when sorting\n            <jats:italic>n<\/jats:italic>\n            elements, the average total number of branch mispredictions is at most \u03f5\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) for some small \u03f5 depending on the block size.\n          <\/jats:p>\n          <jats:p>Our experimental results are promising: when sorting random-integer data, we achieve an increase in speed (number of elements sorted per second) of more than 80% over the GCC implementation of Quicksort (C++ std::sort). Also, for many other types of data and non-random inputs, there is still a significant speedup over std::sort. Only in a few special cases, such as sorted or almost sorted inputs, can std::sort beat our implementation. Moreover, on random-input permutations, our implementation is even slightly faster than an implementation of the highly tuned Super Scalar Sample Sort, which uses a linear amount of additional space.<\/jats:p>\n          <jats:p>Finally, we also apply our approach to Quickselect and obtain a speed-up of more than 100% over the GCC implementation (C++ std::nth_element).<\/jats:p>","DOI":"10.1145\/3274660","type":"journal-article","created":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T12:58:34Z","timestamp":1548853114000},"page":"1-22","source":"Crossref","is-referenced-by-count":15,"title":["BlockQuicksort"],"prefix":"10.1145","volume":"24","author":[{"given":"Stefan","family":"Edelkamp","sequence":"first","affiliation":[{"name":"King\u2019s College London"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7645-5867","authenticated-orcid":false,"given":"Armin","family":"Wei\u00df","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Stuttgart"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,1,30]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"ARMv8 Instruction Set Overview. Retrieved","year":"2018","unstructured":"2011. ARMv8 Instruction Set Overview. Retrieved December 24, 2018 from https:\/\/www.element14.com\/community\/servlet\/JiveServlet\/previewBody\/41836-102-1-229511\/ARM.Reference_Manual.pdf Document number: PRD03-GENC-010197 15.0. 2011. ARMv8 Instruction Set Overview. Retrieved December 24, 2018 from https:\/\/www.element14.com\/community\/servlet\/JiveServlet\/previewBody\/41836-102-1-229511\/ARM.Reference_Manual.pdf Document number: PRD03-GENC-010197 15.0."},{"key":"e_1_2_1_2_1","first-page":"248966","volume-title":"Retrieved","year":"2018","unstructured":"2016. Intel 64 and IA-32 Architecture Optimization Reference Manual . Retrieved December 24, 2018 from http:\/\/www.intel.com\/content\/dam\/www\/public\/us\/en\/documents\/manuals\/64-ia-32-architectures-optimization-manual.pdf Order Number : 248966 - 248032 . 2016. Intel 64 and IA-32 Architecture Optimization Reference Manual. Retrieved December 24, 2018 from http:\/\/www.intel.com\/content\/dam\/www\/public\/us\/en\/documents\/manuals\/64-ia-32-architectures-optimization-manual.pdf Order Number: 248966-032."},{"key":"e_1_2_1_3_1","first-page":"17","article-title":"Engineering of a Quicksort partitioning algorithm","volume":"2","author":"Abhyankar D.","year":"2011","unstructured":"D. Abhyankar and M. Ingle . 2011 . Engineering of a Quicksort partitioning algorithm . Journal of Global Research in Computer Science 2 , 2 (2011), 17 -- 23 . D. Abhyankar and M. Ingle. 2011. Engineering of a Quicksort partitioning algorithm. Journal of Global Research in Computer Science 2, 2 (2011), 17--23.","journal-title":"Journal of Global Research in Computer Science"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2963102"},{"key":"e_1_2_1_6_1","volume-title":"25th Annual European Symposium on Algorithms (ESA\u201917)","volume":"87","author":"Axtmann Michael","year":"2017","unstructured":"Michael Axtmann , Sascha Witt , Daniel Ferizovic , and Peter Sanders . 2017 . In-place parallel super scalar Samplesort (IPSSSSo) . In 25th Annual European Symposium on Algorithms (ESA\u201917) , September 4-6, 2017, Vienna, Austria (LIPIcs), Kirk Pruhs and Christian Sohler (Eds.) , Vol. 87 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 9:1--9:14. Michael Axtmann, Sascha Witt, Daniel Ferizovic, and Peter Sanders. 2017. In-place parallel super scalar Samplesort (IPSSSSo). In 25th Annual European Symposium on Algorithms (ESA\u201917), September 4-6, 2017, Vienna, Austria (LIPIcs), Kirk Pruhs and Christian Sohler (Eds.), Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 9:1--9:14."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1370599"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1227164"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11534273_34"},{"key":"e_1_2_1_10_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2001. Introduction to Algorithms ( 2 nd ed.). The MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001. Introduction to Algorithms (2nd ed.). The MIT Press.","edition":"2"},{"key":"e_1_2_1_11_1","volume-title":"24th Annual European Symposium on Algorithms (ESA\u201916)","volume":"57","author":"Edelkamp Stefan","year":"2016","unstructured":"Stefan Edelkamp and Armin Wei\u00df . 2016 . BlockQuicksort: Avoiding branch mispredictions in Quicksort . In 24th Annual European Symposium on Algorithms (ESA\u201916) , August 22-24, 2016, Aarhus, Denmark (LIPIcs), Piotr Sankowski and Christos D. Zaroliagis (Eds.) , Vol. 57 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 38:1--38:16. Stefan Edelkamp and Armin Wei\u00df. 2016. BlockQuicksort: Avoiding branch mispredictions in Quicksort. In 24th Annual European Symposium on Algorithms (ESA\u201916), August 22-24, 2016, Aarhus, Denmark (LIPIcs), Piotr Sankowski and Christos D. Zaroliagis (Eds.), Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 38:1--38:16."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30347-0_14"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_15"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/355588.365103"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/360680.360694"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/360680.360691"},{"key":"e_1_2_1_17_1","unstructured":"Nikolaj Hass and Mikkel Angaju Rasmussen. 2016. Is Multi-Pivot BlockQuickSort viable? Unpublished student project supervised by Martin Aum\u00fcller.  Nikolaj Hass and Mikkel Angaju Rasmussen. 2016. Is Multi-Pivot BlockQuickSort viable? Unpublished student project supervised by Martin Aum\u00fcller."},{"key":"e_1_2_1_18_1","volume-title":"Patterson","author":"Hennessy John L.","year":"2011","unstructured":"John L. Hennessy and David A . Patterson . 2011 . Computer Architecture : A Quantitative Approach (5th ed.). Morgan Kaufmann . John L. Hennessy and David A. Patterson. 2011. Computer Architecture: A Quantitative Approach (5th ed.). Morgan Kaufmann."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366644"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366647"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_69"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/251040.251053"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.06.032"},{"key":"e_1_2_1_26_1","volume-title":"Sorting and Searching","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1998. Sorting and Searching ( 2 nd ed.). The Art of Computer Programming, Vol . 3. Addison Wesley Longman . Donald E. Knuth. 1998. Sorting and Searching (2nd ed.). The Art of Computer Programming, Vol. 3. Addison Wesley Longman.","edition":"2"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 16th Workshop on Algorithm Engineering and Experiments (ALENEX\u201914)","author":"Kushagra Shrinu","year":"2014","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 Workshop on Algorithm Engineering and Experiments (ALENEX\u201914) , Portland, Oregon , January 5, 2014 , Catherine C. McGeoch and Ulrich Meyer (Eds.). 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 Workshop on Algorithm Engineering and Experiments (ALENEX\u201914), Portland, Oregon, January 5, 2014, Catherine C. McGeoch and Ulrich Meyer (Eds.). SIAM, 47--60."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0985"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790216.2790227"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904)","author":"Martinez Conrado","year":"2004","unstructured":"Conrado Martinez , Daniel Panario , and Alfredo Viola . 2004 . Adaptive sampling for Quickselect . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904) , New Orleans, Louisiana , January 11-14, 2004, J. Ian Munro (Ed.). SIAM, 447--455. http:\/\/dl.acm.org\/citation.cfm?id&equals;982792.982856. Conrado Martinez, Daniel Panario, and Alfredo Viola. 2004. Adaptive sampling for Quickselect. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904), New Orleans, Louisiana, January 11-14, 2004, J. Ian Munro (Ed.). SIAM, 447--455. http:\/\/dl.acm.org\/citation.cfm?id&equals;982792.982856."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798606"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382108"},{"key":"e_1_2_1_33_1","volume-title":"Introspective sorting and selection algorithms. Software\u2014Practice and Experience 27, 8","author":"Musser David R.","year":"1997","unstructured":"David R. Musser . 1997. Introspective sorting and selection algorithms. Software\u2014Practice and Experience 27, 8 ( 1997 ), 983--993. David R. Musser. 1997. Introspective sorting and selection algorithms. Software\u2014Practice and Experience 27, 8 (1997), 983--993."},{"key":"e_1_2_1_34_1","volume-title":"Retrieved","author":"Price Charles","year":"1995","unstructured":"Charles Price . 1995 . MIPS IV Instruction Set . Retrieved December 24, 2018 from http:\/\/math-atlas.sourceforge.net\/devel\/assembly\/mips-iv.pdf Charles Price. 1995. MIPS IV Instruction Set. Retrieved December 24, 2018 from http:\/\/math-atlas.sourceforge.net\/devel\/assembly\/mips-iv.pdf"},{"key":"e_1_2_1_35_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of Algorithms (ESA\u201904)","author":"Sanders Peter","unstructured":"Peter Sanders and Sebastian Winkel . 2004. Super scalar sample sort . In Proceedings of Algorithms (ESA\u201904) , Lecture Notes in Computer Science , Susanne Albers and Tomasz Radzik (Eds.), Vol. 3221 . Springer , Berlin , 784--796. Peter Sanders and Sebastian Winkel. 2004. Super scalar sample sort. In Proceedings of Algorithms (ESA\u201904), Lecture Notes in Computer Science, Susanne Albers and Tomasz Radzik (Eds.), Vol. 3221. Springer, Berlin, 784--796."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289467"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359631"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_71"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629340"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/512274.512284"},{"key":"e_1_2_1_41_1","volume-title":"Retrieved","author":"Yaroslavskiy Vladimir","year":"2009","unstructured":"Vladimir Yaroslavskiy . 2009 . Dual-Pivot Quicksort algorithm . Retrieved December 24, 2018 from http:\/\/codeblab.com\/wp-content\/uploads\/2009\/09\/DualPivotQuicksort.pdf Vladimir Yaroslavskiy. 2009. Dual-Pivot Quicksort algorithm. Retrieved December 24, 2018 from http:\/\/codeblab.com\/wp-content\/uploads\/2009\/09\/DualPivotQuicksort.pdf"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274660","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3274660","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:56Z","timestamp":1750208276000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274660"}},"subtitle":["Avoiding Branch Mispredictions in Quicksort"],"short-title":[],"issued":{"date-parts":[[2019,1,30]]},"references-count":40,"alternative-id":["10.1145\/3274660"],"URL":"https:\/\/doi.org\/10.1145\/3274660","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,30]]}}}