{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T16:39:35Z","timestamp":1775839175871,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,12,9]],"date-time":"2024-12-09T00:00:00Z","timestamp":1733702400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,9]],"date-time":"2024-12-09T00:00:00Z","timestamp":1733702400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,2]]},"DOI":"10.1007\/s00453-024-01285-6","type":"journal-article","created":{"date-parts":[[2024,12,9]],"date-time":"2024-12-09T12:06:44Z","timestamp":1733746004000},"page":"242-291","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Galloping in Fast-Growth Natural Merge Sorts"],"prefix":"10.1007","volume":"87","author":[{"given":"Elahe","family":"Ghasemi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Jug\u00e9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ghazal","family":"Khalighinejad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Helia","family":"Yazdanyar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,9]]},"reference":[{"key":"1285_CR1","unstructured":"Auger, N., Jug\u00e9, V., Nicaud, C., Pivoteau, C.: On the worst-case complexity of Timsort. In: $$26^{{\\rm th}}$$ Annual European Symposium on Algorithms (ESA), vol. 4, pp. 1\u201313 (2018). Extended version available at: arXiv:1805.08612"},{"key":"1285_CR2","unstructured":"Auger, N., Nicaud, C., Pivoteau, C.: Merge strategies: from merge sort to Timsort. Research report hal-01212839 (2015)"},{"key":"1285_CR3","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.tcs.2013.10.019","volume":"513","author":"J Barbay","year":"2013","unstructured":"Barbay, J., Navarro, G.: On compressing permutations and adaptive sorting. Theoret. Comput. Sci. 513, 109\u2013123 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"1285_CR4","unstructured":"Barbay, J., Ochoa, C., Satti, S.R.: Synergistic solutions on multisets. In: $$28^{{\\rm th}}$$ Annual Symposium on Combinatorial Pattern Matching (CPM), vol. 31, pp. 2\u201314 (2017)"},{"key":"1285_CR5","unstructured":"Bayer, P.: Improved bounds on the cost of optimal and balanced binary search trees. M.Sc. Thesis, MIT, Cambridge (1975)"},{"issue":"3","key":"1285_CR6","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/0020-0190(76)90071-5","volume":"5","author":"J Bentley","year":"1976","unstructured":"Bentley, J., Yao, A.: An almost optimal algorithm for unbounded searching. Inf. Process. Lett. 5(3), 82\u201387 (1976)","journal-title":"Inf. Process. Lett."},{"key":"1285_CR7","unstructured":"Bloch, J.: Timsort implementation in Java 13, retrieved 01\/01\/2024. https:\/\/github.com\/openjdk\/jdk\/blob\/master\/src\/java.base\/share\/classes\/java\/util\/ComparableTimSort.java"},{"key":"1285_CR8","doi-asserted-by":"crossref","unstructured":"Buss, S., Knop, A.: Strategies for stable merge sorting. In: Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1272\u20131290 (2019)","DOI":"10.1137\/1.9781611975482.78"},{"key":"1285_CR9","doi-asserted-by":"crossref","unstructured":"Carlsson, S., Levcopoulos, C., Petersson, O.: Sublinear merging and natural mergesort. In: Algorithmica, vol. 9, pp. 629\u2013648 (1993)","DOI":"10.1007\/BF01190160"},{"key":"1285_CR10","unstructured":"Cohen, B.: Timsort implementation in Swift, retrieved 01\/01\/2024. https:\/\/github.com\/apple\/swift\/blob\/master\/stdlib\/public\/core\/Sort.swift"},{"issue":"4","key":"1285_CR11","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1145\/146370.146381","volume":"24","author":"V Estivill-Castro","year":"1992","unstructured":"Estivill-Castro, V., Wood, D.: A survey of adaptive sorting algorithms. ACM Comput. Surv. 24(4), 441\u2013476 (1992)","journal-title":"ACM Comput. Surv."},{"issue":"4","key":"1285_CR12","doi-asserted-by":"publisher","first-page":"622","DOI":"10.1137\/0206045","volume":"6","author":"A Garsia","year":"1977","unstructured":"Garsia, A., Wachs, M.: A new algorithm for minimal binary search trees. SIAM J. Comput. 6(4), 622\u2013642 (1977)","journal-title":"SIAM J. Comput."},{"key":"1285_CR13","doi-asserted-by":"crossref","unstructured":"Gelling, W., Nebel, M., Smith, B., Wild, S.: Multiway powersort. In: Symposium on Algorithm Engineering and Experiments (ALENEX), pp. 190\u2013200 (2023)","DOI":"10.1137\/1.9781611977561.ch16"},{"key":"1285_CR14","unstructured":"Ghasemi, E., Jug\u00e9, V., Khalighinejad, G.: Galloping in fast-growth natural merge sorts. In: $$49^{{\\rm th}}$$ International Colloquium on Automata, Languages, and Programming (ICALP), pp. 68:1\u201368:19 (2022)"},{"issue":"4","key":"1285_CR15","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/0121057","volume":"21","author":"T Hu","year":"1971","unstructured":"Hu, T., Tucker, A.: Optimal computer search trees and variable-length alphabetical codes. SIAM J. Appl. Math. 21(4), 514\u2013532 (1971)","journal-title":"SIAM J. Appl. Math."},{"issue":"4","key":"1285_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3664195","volume":"20","author":"V Jug\u00e9","year":"2024","unstructured":"Jug\u00e9, V.: Adaptive Shivers sort: an alternative sorting algorithm. ACM Trans. Algorithms 20(4), 1\u201355 (2024)","journal-title":"ACM Trans. Algorithms"},{"key":"1285_CR17","unstructured":"Jug\u00e9, V.: Counting comparisons performed by Timsort to merge two non-decreasing runs. https:\/\/github.com\/VincentJuge1987\/timsort"},{"key":"1285_CR18","unstructured":"Knuth, D.: The art of computer programming, Volume 3: ($$2^{{\\rm nd}}$$ Ed.) Sorting and Searching. Addison Wesley Longman Publish. Co. (1998)"},{"key":"1285_CR19","doi-asserted-by":"crossref","unstructured":"Levcopoulos, C., Petersson, O.: Sorting shuffled monotone sequences. In: Scandinavian Workshop on Algorithm Theory, pp. 181\u2013191 (1990)","DOI":"10.1007\/3-540-52846-6_88"},{"issue":"4","key":"1285_CR20","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1109\/TC.1985.5009382","volume":"34","author":"H Mannila","year":"1985","unstructured":"Mannila, H.: Measures of presortedness and optimal sorting algorithms. IEEE Trans. Comput. 34(4), 318\u2013325 (1985)","journal-title":"IEEE Trans. Comput."},{"key":"1285_CR21","unstructured":"McIlroy, P.: Optimistic sorting and information theoretic complexity. In: Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 467\u2013474 (1993)"},{"issue":"1","key":"1285_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0205001","volume":"5","author":"I Munro","year":"1976","unstructured":"Munro, I., Spira, P.: Sorting and searching in multisets. SIAM J. Comput. 5(1), 1\u20138 (1976)","journal-title":"SIAM J. Comput."},{"key":"1285_CR23","unstructured":"Munro, I., Wild, S.: Nearly-optimal mergesorts: fast, practical sorting methods that optimally adapt to existing runs. In: $$26^{{\\rm th}}$$ Annual European Symposium on Algorithms (ESA), pp. 63:1\u201363:15 (2018)"},{"key":"1285_CR24","unstructured":"Peters, T.: Timsort description, retrieved 01\/09\/2021. https:\/\/github.com\/python\/cpython\/blob\/master\/Objects\/listsort.txt"},{"key":"1285_CR25","unstructured":"Renault, C., et al.: Timsort implementation in Rust, retrieved 01\/01\/2024. https:\/\/github.com\/rust-lang\/rust\/blob\/master\/library\/alloc\/src\/slice.rs"},{"key":"1285_CR26","unstructured":"Schou, J., Wang, B.: PersiSort: a new perspective on adaptive sorting based on persistence. In: $$36^{{\\rm th}}$$ Canadian Conference on Computational Geometry (CCCG), pp. 283\u2013297 (2024)"},{"key":"1285_CR27","unstructured":"Shivers, O.: A simple and efficient natural merge sort. Technical report, Georgia Institute of Technology (2002)"},{"key":"1285_CR28","unstructured":"van Rossum, G., et al.: Powersort implementation in CPython, retrieved 01\/01\/2024. https:\/\/github.com\/python\/cpython\/blob\/master\/Objects\/listobject.c"},{"key":"1285_CR29","unstructured":"Weaton, J., M\u00fctzel, M.: Timsort implementation in Octave, retrieved 01\/01\/2024. https:\/\/github.com\/gnu-octave\/octave\/blob\/master\/liboctave\/util\/oct-sort.cc"},{"key":"1285_CR30","unstructured":"Z\u00fcnd, S., et al.: Timsort implementation in V8, retrieved 01\/01\/2024. https:\/\/github.com\/v8\/v8\/blob\/master\/third_party\/v8\/builtins\/array-sort.tq"}],"updated-by":[{"DOI":"10.1007\/s00453-025-01297-w","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T00:00:00Z","timestamp":1738108800000}}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01285-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01285-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01285-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T13:39:02Z","timestamp":1739367542000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01285-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,9]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["1285"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01285-6","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s00453-025-01297-w","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,9]]},"assertion":[{"value":"30 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2025","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original version of the article is corrected: Affiliation of coauthor Helia Yazanyar is corrected.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 January 2025","order":7,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":8,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":9,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00453-025-01297-w","URL":"https:\/\/doi.org\/10.1007\/s00453-025-01297-w","order":10,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no Conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}