1 Introduction
In 2002, Tim Peters, a software engineer, created a new sorting algorithm, which was called TimSort [10]. This algorithm immediately demonstrated its efficiency for sorting actual data, and was adopted as the standard sorting algorithm in core libraries of widespread programming languages such as Python and Java. Hence, the prominence of such a custommade algorithm over previously preferred optimal algorithms contributed to the regain of interest in the study of sorting algorithms.
Among the bestidentified reasons behind the success of TimSort are the fact that this algorithm is well adapted to the architecture of computers (e.g., for dealing with cache issues) and to realistic distributions of data. In particular, the very conception of TimSort makes it particularly wellsuited to sorting data whose run decompositions [3, 5] (see Figure 1) are simple. Such decompositions were already used by Knuth NaturalMergeSort [7, Section 5.2.4], which predated TimSort, and adapted the traditional MergeSort algorithm as follows: NaturalMergeSort is based on splitting arrays into monotonic subsequences, also called runs, and on merging these runs together. Thus, all algorithms sharing this feature of NaturalMergeSort are also called natural merge sorts.
In addition to being a natural merge sort, TimSort also includes many optimisations, which were carefully engineered, through extensive testing, to offer the best complexity performances. As a result, the general structure of TimSort can be split into three main components: (i) a variant of an insertion sort, which is used to deal with small runs (e.g., runs of length less than 32), (ii) a simple policy for choosing which large runs to merge, (iii) a subroutine for merging these runs. The second component has been subject to an intense scrutiny these last few years, thereby giving birth to a great variety of TimSortlike algorithms. On the contrary, the first and third components, which seem more complicated and whose effect may be harder to quantify, have often been used as black boxes when studying TimSort or designing variants thereof.
Context and related work
The success of TimSort has nurtured the interest in the quest for sorting algorithms that would be adapted to arrays with few runs. However, the ad hoc conception of TimSort made its complexity analysis less easy than what one might have hoped, and it is only in 2015, a decade after TimSort had been largely deployed, that Auger et al. proved that TimSort required comparisons for sorting arrays of length [2].
This is optimal in the model of sorting by comparisons, if the input array can be an arbitrary array of length . However, taking into account the run decompositions of the input array allows using finergrained complexity classes, as follows. First, one may consider only arrays whose run decomposition consists of monotonic runs. On such arrays, the best worstcase time complexity one may hope for is [8]. Second, we may consider even more restricted classes of input arrays, and focus only on those arrays that consist of runs of lengths . In that case, the best worstcase time complexity is , where is defined as and is the general entropy function [3, 6].
TimSort enjoys such a time complexity [1]. In fact, since TimSort was invented, several natural merge sorts have been proposed, all of which were meant to offer easytoprove complexity guarantees. Such algorithms include ShiversSort [11], which runs in time ; StackSort [2], which, like NaturalMergeSort, runs in time ; MergeSort [4], PeekSort and PowerSort [9], and the most recent adaptive ShiversSort [6], which, like TimSort, run in time .
Except TimSort, these algorithms are, in fact, described only as policies for merging runs, the actual subroutine used for merging runs being left implicit. In practice, choosing a naive merging subroutine does not harm the worstcase time complexities considered above. As a consequence, all authors identified the cost of merging two runs of lengths and with the sum , and the complexity of the algorithm with the sum of the costs of the merges processed.
One notable exception is that of [9], whose authors compare the running times of TimSort and of TimSort’s variant where the merging subroutine is replaced by a naive routine. While the arrays on which the performance comparisons are performed are chosen to have a low entropy , the authors did not try to identify which arrays could benefit the most from TimSort’s subroutine. As a result, they unsurprisingly observed that TimSort’s complex subroutine seemed less efficient than the naive one, but their work suggests another approach: finding distributions on arrays for which TimSort’s merging subroutine will actually be helpful.
Contributions
We study the time complexity of TimSort and its variants in a context where we refine the family of arrays we consider. This refinement is based on notion of complexity about the input arrays that is dual to the decomposition of arrays into monotonic runs.
Consider an array whose values are pairwise distinct integers between and : we identify with a permutation of the set . In the standard literature, we subdivide into distinct increasing runs, i.e., we partition the set into intervals such that the function is increasing on each interval .
A dual approach would consist in partitioning that set into intervals , which we call dual runs below, such that the function is increasing on each interval . It would then be feasible to sort the array in time , or even , where our intervals have lengths and .
In this preliminary version, we prove that, thanks to its merging subroutine, TimSort requires comparisons. In a subsequent version of this paper, we will further prove that TimSort requires only comparisons.
2 TimSort and its subroutine for merging runs
In this section, we describe the sorting algorithm TimSort and the components it consists of. As mentioned in Section 1, TimSort is based on decomposing its input array into monotonic (nondecreasing) runs, which are then merged together into larger monotonic runs. Following the literature on this subject, we first focus on the policy used by TimSort to decide which runs to merge.
In order to do so, each monotonic run is identified to a pair of pointers to its first and last entries in the array. TimSort discovers its runs onthefly, from left to right, makes them nondecreasing, and inserts them into a stack, which is used to decide which runs should be merged. These actions are performed as described in Algorithm 1.
This description of TimSort relies on two blackbox subroutines for (i) finding a new run and making it nondecreasing, and (ii) merging two runs. The first subroutine works as follows. New runs in the input array are found by using a naive (yet optimal) algorithm, where comparisons are used to detect a new run of length . If is smaller than a given threshold, the run is made artificially longer by absorbing elements to its right. All these steps require a total of comparisons and element moves. Therefore, and although diving into details might give us some insight on the constant hidden in the notation, we choose not to focus on these steps.
The second subroutine is a blend between a naive merging algorithm, which requires comparisons to merge runs of lengths and , and a dichotomybased algorithm, which requires comparisons in the best case, and comparisons in the worst case. TimSort’s merging subroutine includes both algorithms because the constant hidden in the notations is quite larger than , which might slow down TimSort significantly if the dichotomybased algorithm were used alone. This subroutine roughly works as described in Algorithm 2.
In practice, the parameter is initially set to a constant ( in Java), and may change during the algorithm. In this paper, we will abusively assume that is constant throughout the algorithm. Deciding whether our results remain valid when is updated like in TimSort remains an open question so far.
One readily observes that, if we are lucky enough, for instance if each element in is smaller than each element in , only element comparisons will be performed. However, we should not expect to perform less than element moves. Consequently, using this merging subroutine instead of a naive one may be relevant only if the cost of element comparisons is significantly larger than the cost of element (or pointer) moves.
3 Merging arrays with few distinct values
This section is devoted to proving our main result, which is stated in Theorem 3.
TimSort requires element comparisons to sort arrays of length with dual runs.
TimSort is a comparisonbased sorting algorithm. Thus, its behaviour, i.e., the element comparisons and element moves it performs, are invariant under the following transformation: starting from an array of length with dual runs , we create a new array of length with distinct values, such that whenever belongs to the interval . In other words, for comparisonbased sorting algorithms such as TimSort, arrays with dual runs are indistinguishable from arrays with distinct values. Thus, Theorem 3 is in fact equivalent with the following result, which we focus on proving.
TimSort requires element comparisons to sort arrays of length with distinct values.
Our proof is decomposed into three parts, which follow the decomposition of TimSort’s structure into separate components used for deciding which large runs to merge and merging these runs. In subsequent sections, we will then be able to adapt our proofs more easily to derive similar results to other sorting algorithms.
Below, we first focus on the cost of merging two adjacent runs. Then, we will prove structural properties of the merge tree induced by TimSort; we call these properties the fastgrowth and middlegrowth properties. Finally, using these properties and our upper bounds about the cost of individual merges, we will derive Theorem 3.
Before diving into this threestep proof, however, let us first introduce some notation about runs and their lengths, which we will frequently use, and which follows notations used in Algorithm 1. We will commonly denote runs with capital letters, possibly with some index or some adornment, and we will then denote the length of such a run with the same smallcase letter and the same index of adornment. For instance, runs named , , , and will have respective lengths , , , and .
3.1 Merging runs with few distinct values
In the worst case, when merging runs of lengths and , TimSort’s merging subroutine requires element comparisons and element moves. Moreover, as mentioned in Section 1, if two runs have only few distinct values, merging them can require many fewer comparisons. Both these statements are proved now.
Proposition .
Let and be two sorted arrays of lengths and , whose values are elements of the set . TimSort’s subroutine performs element comparisons to merge these two arrays.
Proof.
TimSort’s merging subroutine goes at most times in the if branch of line 2, and at most times in the else branch of line 2. Thus it performs at most times the comparison in line 2. Finally, whenever the subroutine goes through the else branch of line 2, it performs element comparisons. Consequently, TimSort performs element comparisons.
3.2 A fastgrowth property
Like its many variants, TimSort is based on merging adjacent monotonic (often, increasing) runs, either by the means of a naive merging subroutine or by using Algorithm 2. However, this merging subroutine can be used as a black box along with the procedure for choosing which runs to merge, as described in Algorithm 1.
When an array is sorted, its elements belong to runs which will, two by two, be merged with each other. Consequently, each element may undergo several successive merge operations. A convenient way to represent the succession of runs that ever occur while is sorted is the use of a merge tree [3, 9, 6].
The merge tree induced by a natural merge sort algorithm on an array is the binary rooted tree defined as follows. The nodes of are all the runs that were present in the initial array or that resulted from merging two runs. The runs of the initial array are the leaves of , and when two adjacent runs and are merged with each other (the run spanning positions to the left of those of ) into a new run , they respectively form the left and right children of the node .
Such trees ease the task of referring to several runs that might not have occurred simultaneously. In particular, we will often refer to the ^{th} ancestor or a run , which is just itself if , or the parent (in the tree ) of the ^{th} ancestor of if .
Let us introduce now two notions of fast growth. We will then prove that TimSort matches these two notions.
Let be a natural merge sort algorithm. We say that has the fastgrowth property if it satisfies the following statement:
There exist an integer and a real number such that, for every merge tree induced by and every pair of runs and of , if is the ^{th} ancestor of , then .
We also say that has the middlegrowth property if it satisfies the following statement:
There exists a real number such that, for every merge tree induced by , every integer and every run of height in the tree , we have .
Since every node of height in a merge tree is a run of length at list , it comes at once that every algorithm with the fastgrowth property also has the middlegrowth property. However, we still wanted to introduce these two notions simultaneously. Indeed, we will reuse the notion of fastgrowth in subsequent sections, with stronger results than for algorithm that only enjoy the middlegrowth property. In addition, our proof that TimSort has the middlegrowth property is based on proving that it has the fastgrowth property, due to the following result.
Proposition .
Let be a merge sort generated by TimSort, and let and be two runs in . If is the ^{th} ancestor of , then .
In order to prove Proposition 3.2, we will need do distinguish merges according to the case (from #1 to #4) that triggered them. In particular, although cases #2 to #4 all lead to merging the runs and , we still distinguish these merges. Below, we say that a merge triggered by case #, for , is an #merge. It may also be convenient to group some classes of merges. For instance, we say that a merge is a merge if it was triggered by one of the cases #2 to #4, or that is a merge if it was triggered by one of the cases #1, #2 or #4.
For each type of merge #, we also say that is a #left (respectively, a #right) run if is the left (respectively, right) child of its parent in the tree , and was merged during a #merge. If knowing # is irrelevant, we may also refer directly to left and right runs.
We split the proof of Proposition 3.2 into several lemmas, all of which take place in the following setting. Borrowing notations from [1] and from Algorithm 1, we will look at the runs simultaneously present in a stack just before the run is merged. Here, is the ^{th} bottommost run of the stack and is the length of the run . Similarly, we denote by the length of a run named , and so on. We will also denote by the ^{th} ancestor or the run , so that and , and by the length of .
Let us now mention a series of results that will pave the way towards proving Proposition 3.2. Lemma 3.2 is a mere rephrasing of [1, Lemma 5], hence we omit its proof, while the results of subsequent Lemmas 3.2 to 3.2 are novel.
We have (i) for all , (ii) , (iii) and (iv) .
From Lemma 3.2 follow immediately the inequalities (v) .
If is a right run, then .
Proof.
Let be the left sibling of the run , and let be the integer such that . If , then (iii) shows that . If , then (ii) shows that . In both cases, the run descends from , and thus .
Finally, if , then is a right run, which means both that and that descends from . It follows that . ∎
If is a left run, then .
Proof.
We treat three cases independently, depending on whether is a #1, #2 or #4left run. In each case, we assume that is a left run, unless what Lemma 3.2 proves that .

If is a #1left run, then is merged with and . Since is a left run, descends from , and thus .

If is a #2left run, then is merged with and . It follows that .
∎
If , , and are #3left runs, then .
Proof.
Let and be the two runs placed to the left of ( is the left neighbour of , which is the left neighbour of ) when is merged, and let be the largest integer such that descends from . We define similarly the runs and , and denote by the largest integer such that descends from .
Since is a #3left run, we know that and that . Thus, our next journey through the loop of lines 1 to 1 must trigger another merge, which must be a #1merge since is a left run. This means that and that descends from , so that .
Let us now repeat this argument twice. Since and are #3left runs, we know that , that descends from , and thus that . Then, since and are #3runs, we know again that . Thus, we derive from the inequalities (i) to (v) that . ∎
Proof of Proposition 3.2.
3.3 Sorting arrays with few element comparisons
We prove below that every natural merge sort algorithm with the middlegrowth property requires few element comparisons to sort arrays with few values, if they use TimSort’s merging subroutine. This assertion is more precisely stated in the following result, which we are then devoted to proving.
Proposition .
Let be a natural merge sort algorithm with the middlegrowth property that uses TimSort’s merging subroutine. This algorithm requires element comparisons to sort arrays of length with distinct values.
Note that, since we proved in Section 3.2 that TimSort has the middlegrowth property, Theorem 3 will immediately follow from Proposition 3.3.
Let be a merge tree induced by a natural merge sort algorithm on some array of length . Let be a family of runs in that are pairwise incomparable for the ancestor relation, i.e., such that no run is the ancestor of another run . It holds that .
Proof.
The runs of to which a given position in the array belongs form a chain for the ancestor relation. Thus, the runs in cover pairwise disjoint intervals of the array . This completes the proof. ∎
Proof of Proposition 3.3.
Let be the real number mentioned in the definition of the statement “ has the middlegrowth property” such as described in Definition 3.2. Let be an array of length with distinct values, and let be the merge tree induced by when sorting . Then, for all , let be the family of runs at height in .
We associate each run of height with the number of element comparisons, noted , performed by TimSort’s merging subroutine during the merge that resulted in the run . Proposition 3.1 states that , where the function is defined by .
We extend this notation and, for all , we define the number as the sum of the numbers for those numbers that belong to . Observe that, if is a tree of height , then the algorithm must have performed comparisons to sort . It remains to prove that .
We do so by distinguishing to cases:

If , we simply have , and Lemma 3.3 proves that the latter sum is not larger than .

If , by definition of , we know that every run is of length . Since the function is decreasing the interval , it follows that for all . Hence, Lemma 3.3 proves that .
Setting , we conclude that
Since the series is convergent, this shows that is , i.e., is , thereby completing the proof. ∎
4 Fast or middlegrowth property in other natural merge sorts
Once equipped with Propositions 3.1 and 3.3, we can readily adapt our proof of Theorems 3 and 3 to a wide range of natural merge sort algorithms. Indeed, it suffices to replicate the results of Section 3.2 and to prove that these algorithms have the middlegrowth property.
In this section, we focus on the algorithms we mentioned in Section 1, thereby advocating for the use of TimSort’s merging subroutine in all these algorithms. In each case, we identify the algorithm with its strategy for deciding which runs to merge, implicitly using TimSort’s merging subroutine to perform these merges.
Below, and depending on the context, we may denote by the ^{th} leftmost run of an array to be sorted, or the ^{th} bottommost run of a stack. In each case, we will make our convention explicit, and we will denote the length of the run by . In addition, when focusing on a given array , we will denote by the ^{th} ancestor of the run , and we will denote the length of the run by .
4.1 Algorithms with the fastgrowth property
4.1.1 The algorithm MergeSort
The algorithm MergeSort is presented in Algorithm 3. Our proof follows a path similar to the one used in Section 3.2: it relies on variants of Lemmas 3.2 to 3.2, and culminates with proving the following result.
Proposition .
Consider some real parameter . Let be a merge sort generated by MergeSort, and let and be two runs in . If is the ^{th} ancestor of , then , where we set and .
First, Lemma 4.1.1 strengthens a result that already appears in the proof of [4, Theorem 14], but that contains only the inequalities (vi).
Let be a stack obtained during an execution of MergeSort. We have (vi) whenever and (vii) .
Proof.
We prove, by a direct induction on the number of (push or merge) operations performed before obtaining the stack , that satisfies (vi) and (vii).
First, (vi) and (vii) trivially hold if , as is the case when the algorithm starts. Then, when a stack obeying (vi) and (vii) is transformed into a stack

by inserting a run, then , and for all , which is actually even stronger than required;

by merging two runs, then , and for all , so that satisfies (vi), whereas also satisfies (vii) because
In both cases, satisfies (vi) and (vii), which completes the induction and the proof. ∎
Lemmas 4.1.1 to 4.1.1 focus on inequalities involving the lengths of a given run and its ancestors. In each case, we denote by
the stack at the moment where the run
is merged, and we will use this naming convention when proving these Lemmas.If is a right run, then .
Proof.
Let be the left sibling of the run , and let be the integer such that . If , then (vi) shows that . If , then (vii) shows that . In both cases, the run descends from , and thus .
Finally, if , then is a right run, which means both that and that descends from . It follows that . ∎
If is a left run, then .
Proof.
We treat three cases independently, depending on whether is a #1 or #2left run. In each case, we assume that is a left run, unless what Lemma 4.1.1 proves that .

If is a #1left run, then is merged with and . Since is a left run, descends from , and thus .

If is a #2left run, then is merged with , , and therefore .
∎
If all of , , , …, are #3left runs, then .
Proof.
Our proof is entirely similar to that of Lemma 3.2. For all , let and be the two runs placed to the left of when is merged, and let be the largest integer such that descends from .
Since is a #3left run, we know that and that . Thus, our next journey through the loop of lines 1 to 1 must trigger another merge, which must be a #1merge since is a left run. This means that and that descends from , so that .
Repeating the same argument over and over, we find that and that whenever . Thus, we derive from the inequalities (vi) and (vii) that . ∎
Proof of Proposition 4.1.1.
4.1.2 The algorithm PeekSort
The algorithm PeekSort is not stackbased, and the description that its authors provide is topdown [9, Section 3.1] instead of bottomup like Algorithms 1 and 3. From their description, we derive immediately the following characterisation of the merge trees induced by PeekSort, and which could be considered as an alternative (abstract, underspecified) definition.
Let be a merge sort generated by PeekSort, and let be its leaves, ordered from left to right. Let be an internal node (i.e., run) of , and let and be its left and right children. Finally, let be the rightmost leaf of that descends from , and let be the leftmost leaf of that descends from . It holds that .
Proposition .
Let be a merge sort generated by PeekSort, and let and be two runs in . If is the ^{th} ancestor of , then .
Proof.
Since lefttoright and righttoleft orientations play symmetric roles in Definition 4.1.2, we assume without loss of generality that a majority of the runs , and are left runs.
Let be the two smallest integers such that and are left runs, and let and be their right siblings. The rightmost leaf of that descends from also descends from , and thus its length is at most . Hence, it follows from Definition 4.1.2 that , and thus . ∎
4.1.3 The algorithm PowerSort
Like its sibling PeekSort, the algorithm PowerSort is not stackbased, and the description that its authors provide is topdown [9, Section 3.2]. This algorithm is based on the ad hoc notion of power of a run, which is defined as follows.
Let be a merge sort generated by PeekSort when sorting an array of length (which spans positions numbered from to ), and let be its leaves, ordered from left to right. Let be an internal node (i.e., run) of , and let and be its left and right children. Finally, let be the rightmost leaf of that descends from , and let be the leftmost leaf of that descends from .
The power of is the largest integer such that there exists an integer satisfying the inequalities .
Note that the power of a leaf is not defined. Based on the notion of power, we use now [9, Lemma 4] as our alternative (abstract, and quite underspecified) definition of PowerSort.
Let be a merge sort generated by PowerSort, and let and be two runs in , with powers and . If is the parent of , then .
Proposition .
Let be a merge sort generated by PowerSort, and let and be two runs in . If is the ^{th} ancestor of , then .
Proving Proposition 4.1.3 is slightly more complicated than proving Proposition 4.1.2. Our proof is based on the following result.
Let be a run of power . It holds that and that .
Proof.
In what follows, we always denote by the sum , and by the number . Then, we prove the two desired inequalities separately.
First, let be the leaves of that descend from , and let be the rightmost leaf that descends from the left child of . By maximality of in Definition 4.1.3, we know that and that . This means that there exists an odd integer such that and .
Now, consider some integer . Let be the least common ancestor of and , and let be its power. Since descends from the left child of , we know that . By maximality of , this means that . This equality is valid whenever , and thus .
When , the same reasoning proves that . It follows that the run has length
Second, let be the rightmost leaf that descends from the left child of . Since is a run of power , we know that , and therefore there exists an even integer such that . Since and have opposite parities, they are distinct from each other, and thus . By construction, both runs and descend from . It follows that the run has length
Comments
There are no comments yet.