AIOJ

This page introduces Timsort, a hybrid, stable sorting algorithm.

Introduction

Timsort was designed by Tim Peters, a core developer of Python, in 2002 and applied to the Python language. It cleverly combines the advantages of insertion sort and merge sort, precisely optimizing for the existing order in a data set, and is especially suitable for data sets containing many partially ordered subsequences. Since Python 2.3, Timsort has been selected as the default sorting algorithm of the Python standard library and has been widely used in other programming environments, for example, for sorting arrays of non-primitive objects in Java SE 7.

Steps

The core idea of Timsort is to improve sorting efficiency by identifying and exploiting order already present in the data set. Its main steps include:

Identify Runs: Scan the array to be sorted and identify ordered contiguous subsequences (Runs).
Extend Runs: If the identified Run is shorter than MIN_RUN, extend it using insertion sort.
Merge Runs: Timsort maintains a special stack and uses a specific merging strategy to combine the Runs already in the stack into larger ordered sequences.

Identifying Runs

First, Timsort scans the array from left to right to identify contiguous ordered sequences. These ordered sequences are called Runs:

Ascending Run: If the next element is greater than or equal to the previous element, continue extending the Run.
Descending Run: If the next element is less than the previous element, continue extending the Run, and then reverse the Run into ascending order.

Extending Runs

To improve the sorting efficiency for small data sets, Timsort introduces a minimum Run length, MIN_RUN. Its value is generally calculated dynamically according to the length of the array to be sorted, and is usually between $32$ and $64$ .

If the identified Run has length greater than or equal to MIN_RUN, no additional operation is needed; push the Run directly onto the stack.
If the identified Run has length less than MIN_RUN, use binary insertion sort to insert subsequent elements of the Run into the Run until its length reaches MIN_RUN, and then push it onto the stack.

Merging Runs

In Timsort, merge sort is managed and controlled through a stack. The stack stores the ordered Runs that have already been identified and controls the merging of Runs in the stack through specific merge rules. Its purpose is to maintain balance and stability during merging.

Merge rules

Timsort is a stable sorting algorithm, meaning that equal elements retain their original relative order after sorting. To ensure this, Timsort merges only adjacent, contiguous Runs during merging, rather than directly merging non-adjacent Runs. This is because non-adjacent Runs may contain equal elements, and directly merging them is very likely to disrupt their relative order.

At the same time, to ensure balanced merging, Timsort introduces specific merge rules. Before each merge operation, the algorithm checks the top three Runs X, Y, and Z on the stack to ensure that the following two conditions hold:

Condition 1: len(Z) > len(Y) + len(X)
Condition 2: len(Y) > len(X)

If the three Runs at the top of the stack do not satisfy the above conditions, Timsort merges Y with the smaller of X and Z, and then checks the conditions again. Once the conditions are satisfied, it continues searching for new Runs, adds them to the stack, and begins the next round of merging.

Merge Rules

Merge optimization

To improve efficiency and reduce space overhead when merging Runs of different lengths, Timsort uses binary search before merging to precisely locate the range of elements that needs to be processed, and merges only the part that needs to be moved. Specifically:

Determine insertion points: Use binary search to find the insertion position in the first Run of the first element of the second Run, and the insertion position in the second Run of the last element of the first Run. This narrows the range that needs to be merged, so only the elements that need to be moved are processed.
Temporary buffer: Traditional in-place merge algorithms are too inefficient and require a large number of element moves. To reduce this overhead, Timsort uses a temporary buffer: it copies the shorter Run into the buffer, and then gradually copies elements from the buffer back into the original array.

For example, suppose there are two Runs, A and B:

Run A: $[1, 2, 3, 6, 10]$
Run B: $[4, 5, 7, 9, 12, 14, 17]$

Through binary search, we can determine:

Element $4$ should be inserted at the fourth position of Run A.
Element $10$ should be inserted at the fifth position of Run B.

Therefore, the first $3$ elements of Run A and the last $3$ elements of Run B are already in their correct positions and do not need to be processed. We only need to merge Run A's $[6, 10]$ and Run B's $[4, 5, 7, 9]$ . The merging process is shown in the figure below:

Timsort Merge

Galloping mode

To further improve merge efficiency, Timsort introduces Galloping Mode. In the standard merge process, the algorithm compares the elements in the two Runs one by one and places the smaller element into the result array. However, if one Run contains many consecutive elements smaller than the current element of the other Run, comparing them one by one causes unnecessary overhead.

To solve this problem, Timsort sets a threshold, Min_Gallop (default value $7$ ). When the number of consecutive wins by the elements in one Run reaches Min_Gallop, the algorithm enters galloping mode to quickly locate element positions. Its specific steps are as follows:

Exponential search: Starting from the current position, the algorithm searches in one Run with exponentially increasing step lengths $(1, 2, 4, 8, \dots)$ until it finds an interval containing the target element.
Binary search: Once the interval containing the target element has been determined, the algorithm uses binary search within that interval to locate the target element precisely.

In this way, Timsort can skip a large number of unnecessary comparisons and quickly process consecutive smaller (or larger) elements in one Run, moving them in batches into the merged result.

However, galloping mode is not more efficient in every situation. Under some data distributions, galloping mode may result in more comparisons. Therefore, Timsort uses a dynamic adjustment strategy:

Threshold adjustment: Maintain a variable Min_Gallop parameter. When galloping mode performs well (that is, elements are selected from the same Run many times in a row), decrease Min_Gallop by $1$ to encourage continued use of galloping mode; when galloping mode performs poorly (frequent switching between the two Runs), increase Min_Gallop by $1$ to reduce the frequency of using galloping mode.

By dynamically adjusting the value of Min_Gallop, the algorithm can balance ordinary merge mode and galloping mode according to the actual data. For partially ordered or highly ordered data, galloping mode can significantly improve efficiency, bringing Timsort's performance close to $O(n)$ ; for random data, the algorithm gradually tends toward ordinary merging, thereby ensuring a time complexity of $O(n \log n)$ .

Complexity

The time complexity of Timsort depends on how ordered the data is:

Best case: $O(n)$ $O (n)$
- When the data is already sorted or nearly sorted, the lengths of the Runs identified by the algorithm are close to $n$ , the number of merges is reduced, and the complexity approaches $O(n)$ .
Worst case: $O(n \log n)$ $O (n lo g n)$
- When the data is completely unordered, each Run has length close to $1$ , so $O(\log n)$ merges are needed, each merge costs $O(n)$ , and the total complexity is $O(n \log n)$ .

Proof:

Identifying and extending Runs:
- Identifying Runs requires one linear traversal of the array, with complexity $O(n)$ .
- Extending Runs using insertion sort also requires a linear traversal of the array, with complexity $O(n)$ .
Merging Runs:
- The total number of merge operations is related to the total number of Runs. In the worst case, the number of Runs is n / MIN_RUN; since MIN_RUN is a constant, the number of Runs can be regarded as $O(n)$ .
- $O(n)$ Runs require $O(\log n)$ merge operations, each merge costs $O(n)$ , so the total complexity of the merge operations is $O(n \log n)$ .

As for space complexity, since Timsort roughly needs an additional $O(n)$ space to store the stack and temporary buffer, the total space complexity is $O(n)$ .

Implementation

Pseudocode implementation

\begin{array}{ll} 1 & nRemaining \gets \text{数组长度} \\ 2 & minRun \gets \text{选择合适的 MinRun 的值}(nRemaining) \\ 3 & startIndex \gets 0 \\ 4 & \textbf{while } nRemaining > 0 \ \textbf{do} \\ 5 & \qquad runLength \gets \text{识别 Run }(array, startIndex, nRemaining) \\ 6 & \qquad \textbf{if } runLength < minRun \ \textbf{then} \\ 7 & \qquad \qquad extendLength \gets \min(minRun, nRemaining) \\ 8 & \qquad \qquad \text{使用插入排序扩展区间 } [startIndex, startIndex + extendLength - 1]\\ 9 & \qquad \qquad runLength \gets extendLength \\ 10 & \qquad \textbf{end if} \\ 11 & \qquad \text{将 Run } (startIndex, runLength) \text{ 压入栈中} \\ 12 & \qquad \textbf{调用 } \text{mergeCollapse(栈)} \ \text{检查并合并栈中的 Run } \\ 13 & \qquad startIndex \gets startIndex + runLength \ \text{更新起始位置} \\ 14 & \qquad nRemaining \gets nRemaining - runLength \ \text{更新剩余长度} \\ 15 & \textbf{end while} \\ 16 & \textbf{调用 } \text{mergeForceCollapse(栈)} \ \text{对栈中所有 Run 进行最终的合并} \\ \end{array}

Timsort