{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T04:42:37Z","timestamp":1782967357421,"version":"3.54.5"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T00:00:00Z","timestamp":1722816000000},"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":[[2024,10,31]]},"abstract":"<jats:p>\n            We present a new sorting algorithm, called\n            <jats:monospace>adaptive ShiversSort<\/jats:monospace>\n            , that exploits the existence of monotonic runs for sorting efficiently partially sorted data. This algorithm is a variant of the well-known algorithm\n            <jats:monospace>TimSort<\/jats:monospace>\n            , which is the sorting algorithm used in standard libraries of programming languages, such as Python or Java (for non-primitive types). More precisely,\n            <jats:monospace>adaptive ShiversSort<\/jats:monospace>\n            is a so-called\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -aware merge-sort algorithm, a class that captures \u2018\n            <jats:monospace>TimSort<\/jats:monospace>\n            -like\u2019 algorithms and that was introduced by Buss and Knop.\n          <\/jats:p>\n          <jats:p>\n            In this article, we prove that, although\n            <jats:monospace>adaptive ShiversSort<\/jats:monospace>\n            is simple to implement and differs only slightly from\n            <jats:monospace>TimSort<\/jats:monospace>\n            , its computational cost, in number of comparisons performed, is optimal within the class of\n            <jats:italic>natural<\/jats:italic>\n            merge-sort algorithms, up to a small additive linear term. This makes\n            <jats:monospace>adaptive ShiversSort<\/jats:monospace>\n            the first\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -aware algorithm to benefit from this property, which is also a 33% improvement over\n            <jats:monospace>TimSort<\/jats:monospace>\n            's worst-case. This suggests that\n            <jats:monospace>adaptive ShiversSort<\/jats:monospace>\n            could be a strong contender for being used instead of\n            <jats:monospace>TimSort<\/jats:monospace>\n            .\n          <\/jats:p>\n          <jats:p>\n            Then, we investigate the optimality of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -aware algorithms. We give lower and upper bounds on the best approximation factors of such algorithms, compared to optimal stable natural merge-sort algorithms. In particular, we design generalisations of\n            <jats:monospace>adaptive ShiversSort<\/jats:monospace>\n            whose computational costs are optimal up to arbitrarily small multiplicative factors.\n          <\/jats:p>","DOI":"10.1145\/3664195","type":"journal-article","created":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T15:44:49Z","timestamp":1716392689000},"page":"1-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Adaptive Shivers Sort: An Alternative Sorting Algorithm"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0834-9082","authenticated-orcid":false,"given":"Vincent","family":"Jug\u00e9","sequence":"first","affiliation":[{"name":"LIGM (UMR 8049), CNRS, Universit\u00e9 Gustave Eiffel, Marne-la-Vall\u00e9e, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,8,5]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"4:1","volume-title":"Proceedings of the 26th Annual European Symposium on Algorithms (ESA \u201918)","author":"Auger Nicolas","year":"2018","unstructured":"Nicolas Auger, Vincent Jug\u00e9, Cyril Nicaud, and Carine Pivoteau. 2018. On the worst-case complexity of Timsort. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA \u201918). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 4:1\u20134:13. Retrieved from https:\/\/arxiv.org\/abs\/1805.08612"},{"key":"e_1_3_2_3_2","volume-title":"Merge Strategies: From Merge Sort to Timsort","author":"Auger Nicolas","year":"2015","unstructured":"Nicolas Auger, Cyril Nicaud, and Carine Pivoteau. 2015. Merge Strategies: From Merge Sort to Timsort. Research Report hal-01212839. HAL."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.10.019"},{"key":"e_1_3_2_5_2","unstructured":"Josh Bloch. 2021. Timsort Implementation in Java. Retrieved from https:\/\/github.com\/openjdk\/jdk\/blob\/3afeb2cb4861f95fd20c3c04f04be93b435527c0\/src\/java.base\/share\/classes\/java\/util\/ComparableTimSort.java"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.78"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21690-4_16"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-7893-5_1"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/146370.146381"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206045"},{"key":"e_1_3_2_11_2","volume-title":"Planning and Coding of Problems for an Electronic Computing Instrument","author":"Goldstine Herman","year":"1947","unstructured":"Herman Goldstine and John von Neumann. 1947. Planning and Coding of Problems for an Electronic Computing Instrument. Research Report, Institute for Advanced Study."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90088-Q"},{"issue":"7","key":"e_1_3_2_13_2","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/366622.366644","article-title":"Algorithm 64: Quicksort","volume":"4","author":"Hoare Tony","year":"1961","unstructured":"Tony Hoare. 1961. Algorithm 64: Quicksort. Communications of the ACM 4, 7 (1961), 321.","journal-title":"Communications of the ACM"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0121057"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.101"},{"key":"e_1_3_2_16_2","volume-title":"The Art of Computer Programming","author":"Knuth Donald","year":"1998","unstructured":"Donald Knuth. 1998. The Art of Computer Programming, Volume 3 (2nd ed.) Sorting and Searching. Addison Wesley Longman Publish. Co., Redwood City, CA.","edition":"2"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.5009382"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/230588.230594"},{"key":"e_1_3_2_19_2","first-page":"63:1","volume-title":"Proceedings of the 26th Annual European Symposium on Algorithms (ESA \u201918)","author":"Ian Munro J.","year":"2018","unstructured":"J. Ian Munro and Sebastian Wild. 2018. Nearly-optimal mergesorts: Fast, practical sorting methods that optimally adapt to existing runs. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA \u201918). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 63:1\u201363:15."},{"key":"e_1_3_2_20_2","unstructured":"Tim Peters. 2021. Timsort Description . Retrieved from https:\/\/github.com\/python\/cpython\/blob\/e5c8ddb1714fb51ab1defa24352c98e0f01205dc\/Objects\/listsort.txt"},{"key":"e_1_3_2_21_2","volume-title":"A Simple and Efficient Natural Merge Sort","author":"Shivers Olin","year":"2002","unstructured":"Olin Shivers. 2002. A Simple and Efficient Natural Merge Sort. Technical Report. Georgia Institute of Technology."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03816-7_59"},{"key":"e_1_3_2_23_2","unstructured":"Guido van Rossum and 69 Other Contributors. 2021. Timsort Implementation in CPython . Retrieved from https:\/\/github.com\/python\/cpython\/blob\/e5c8ddb1714fb51ab1defa24352c98e0f01205dc\/Objects\/listobject.c"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/512274.512284"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3664195","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3664195","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:44:02Z","timestamp":1750272242000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3664195"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,5]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1145\/3664195"],"URL":"https:\/\/doi.org\/10.1145\/3664195","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,5]]},"assertion":[{"value":"2020-06-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-30","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}