Search Results

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.