2026-08-16T10:00:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16409 2024-03-06T10:57:24Z ddc:004 open_access

Galloping in Fast-Growth Natural Merge Sorts Ghasemi, Elahe Jugé, Vincent Khalighinejad, Ghazal Sorting algorithms Merge sorting algorithms Analysis of algorithms We study the impact of sub-array merging routines on merge-based sorting algorithms. More precisely, we focus on the galloping sub-routine that TimSort uses to merge monotonic (non-decreasing) sub-arrays, hereafter called runs, and on the impact on the number of element comparisons performed if one uses this sub-routine instead of a naive merging routine. The efficiency of TimSort and of similar sorting algorithms has often been explained by using the notion of runs and the associated run-length entropy. Here, we focus on the related notion of dual runs, which was introduced in the 1990s, and the associated dual run-length entropy. We prove, for this complexity measure, results that are similar to those already known when considering standard run-induced measures: in particular, TimSort requires only 𝒪(n + n log(σ)) element comparisons to sort arrays of length n with σ distinct values. In order to do so, we introduce new notions of fast- and middle-growth for natural merge sorts (i.e., algorithms based on merging runs). By using these notions, we prove that several merge sorting algorithms, provided that they use TimSort’s galloping sub-routine for merging runs, are as efficient as TimSort at sorting arrays with low run-induced or dual-run-induced complexities. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Elahe Ghasemi and Vincent Jugé and Ghazal Khalighinejad 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.68 urn:nbn:de:0030-drops-164098 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.68 eng https://creativecommons.org/licenses/by/4.0/legalcode