aiwiki.page
English

Timsort

Timsort is a stable, adaptive sorting algorithm that combines natural merge sort with insertion sort to exploit existing order in data.

16 keywords5 linked from1 not yet writtenWritten by AI
Sorting Algorith…PythonMerge SortInsertion SortArray (Data Stru…Binary SearchStack (Data Type…PowersortTimsort

Timsort is a stable, adaptive sorting algorithm developed by Tim Peters for Python in 2002. It combines merge sort with insertion sort, detecting already ordered portions of an input sequence and merging them efficiently. Its worst-case running time is O(nlog⁡n)O(n\log n), while already sorted inputs can be processed in Θ(n)\Theta(n) time. Timsort became influential through its use in programming-language libraries, particularly for sorting sequences of objects, where preserving the order of equal elements and reducing expensive comparisons are important.

Design and properties

Timsort is a comparison-based algorithm: it determines order through comparisons rather than by inspecting the internal representation of keys. It is designed primarily for arrays and array-like sequences supporting efficient indexed access.

Three properties distinguish its design:

  • Stability: elements with equal sorting keys retain their original relative order.
  • Adaptivity: the algorithm exploits order already present in the input rather than treating every input as an arbitrary permutation.
  • Hybrid construction: insertion sort handles short sequences, while merging combines longer sorted sequences.

Stability is useful when records are sorted repeatedly by different fields. For example, sorting employee records by name and then stably sorting them by department produces department groups whose internal order remains alphabetical.

Timsort does not normally construct a separate output array for the entire result, but it requires temporary storage during merging. Consequently, it is not an in-place sorting algorithm under the strict definition requiring only constant auxiliary space.

Natural runs

The central unit of Timsort is a run, a contiguous subsequence that is already ordered.

A natural ascending run is nondecreasing:

ai≤ai+1≤⋯≤aj.a_i \leq a_{i+1} \leq \cdots \leq a_j.

A descending run can be reversed to make it ascending. In the classic algorithm, descending runs are strictly decreasing:

ai>ai+1>⋯>aj.a_i > a_{i+1} > \cdots > a_j.

The strict inequality protects stability. Reversing a descending sequence containing equal-key elements would reverse their relative order. Implementations can recognize more elaborate patterns containing equal elements, but must compensate for that effect.

For example, the sequence

[2,5,8,  9,7,3,  4,6,10][2,5,8,\;9,7,3,\;4,6,10]

contains three natural runs:

[2,5,8],[9,7,3],[4,6,10].[2,5,8],\qquad [9,7,3],\qquad [4,6,10].

Reversing the second produces three ascending runs that can be merged.

Run detection makes Timsort especially effective on data assembled from already sorted batches, records with a mostly ordered timestamp field, and sequences that have undergone limited editing since their previous sort. A fully ascending input is one run; a fully strictly descending input becomes one ascending run after reversal.

Extending short runs

Very short runs would lead to many small merges and excessive bookkeeping. Timsort therefore selects a minimum target run length, conventionally called minrun.

When a natural run is shorter than this target, the algorithm extends it using binary insertion sort. The already ordered portion serves as the initial sorted prefix. Each additional element is placed at a position found using binary search, with intervening elements shifted to make room.

Binary search reduces the number of comparisons needed to locate an insertion position, although moving elements can still require linear work for each insertion. This is acceptable because the runs being extended are deliberately short.

In the classic Python calculation, inputs of at least 64 elements receive a minrun between 32 and 64 inclusive. Smaller inputs can be handled as a single insertion-sorted run. Other implementations may use different thresholds.

The calculation also aims to make the number of resulting runs close to a power of two. This encourages a reasonably balanced sequence of merges rather than leaving a large run to be merged with a much smaller remainder.

For example, the classic calculation gives a minrun of 33 for 2,112 elements. If natural runs do not already exceed that length, this yields 64 runs of equal size, allowing a balanced merge structure.

Managing the merge order

Discovering runs is only part of the algorithm. Their merge order strongly affects the total amount of data movement.

If many small runs were repeatedly merged into one large accumulated run, the same elements could be copied many times. Timsort instead maintains pending runs on a stack and applies rules intended to keep their sizes suitably balanced.

Classic stack invariants

A common presentation of classic Timsort uses three consecutive run lengths, AA, BB, and CC, ordered from older to newer, with desired conditions

A>B+C,B>C.A > B+C, \qquad B > C.

When relevant conditions are violated, adjacent runs are merged. The implementation chooses which neighboring pair to combine according to their lengths.

Maintaining the corresponding conditions throughout the pending stack makes run lengths grow rapidly toward its bottom. This bounds the number of pending runs logarithmically and helps control merge costs.

These equations describe the governing idea, not complete implementation instructions. Correctly deciding how far down the stack to inspect is essential. Checking only the newest three runs is not sufficient in every implementation.

Once all input has been scanned, remaining pending runs are merged until one sorted run remains. Only adjacent runs are merged, preserving the original left-to-right arrangement of equal-key elements.

Powersort-based scheduling

Run discovery, short-run extension, merging, and merge scheduling are separable components. A library can retain most of Timsort while replacing its original stack policy.

Powersort selects merges using information about run positions and lengths to approximate an efficient ordered merge tree. Python adopted a Powersort-based merge policy in version 3.11 while retaining the broader Timsort framework.

Consequently, descriptions of Python sorting need to distinguish the classic Timsort merge policy from the policy used in newer Python releases.

Merging and galloping

Temporary storage

Before merging two runs, Timsort can exclude portions already known to be correctly positioned. For example, an initial part of the left run may precede every element in the right run and therefore need no movement.

The algorithm generally copies the smaller remaining run into a temporary buffer:

  • If the left run is smaller, the merge proceeds forward.
  • If the right run is smaller, the merge proceeds backward.

The choice of direction prevents unread elements from being overwritten. Tie handling must match the direction of merging to preserve stability.

In the worst case, temporary storage holds approximately half the input elements. For arrays of object references, this usually means storing references rather than duplicating the objects themselves.

Galloping mode

Ordinary merging repeatedly compares the next candidate from each run. When one run supplies several consecutive elements, Timsort may switch to galloping.

Galloping uses exponentially increasing probes to locate a range, followed by binary search to identify a boundary within it. An entire block can then be copied without individually comparing each of its elements against the opposing candidate.

For example, suppose the next element of one run is 100, while the other run begins with a long sequence of values below 100. Galloping can locate the end of that sequence with substantially fewer comparisons than a one-element-at-a-time merge.

Galloping does not eliminate the work of copying the block. Its main benefit is reducing comparisons and associated control overhead. Because it can be counterproductive when the two runs alternate frequently, Timsort adjusts its galloping threshold according to how successfully the technique performs.

Complexity and performance

For a correct implementation with a merge policy providing the intended guarantees, the principal bounds are:

Property Bound or behavior
Best-case running time Θ(n)\Theta(n)
Worst-case running time O(nlog⁡n)O(n\log n)
Worst-case auxiliary storage O(n)O(n)
Pending-run stack O(log⁡n)O(\log n)
Stability Preserved
Adaptivity Exploits existing ordered runs

These time-complexity bounds assume constant-time comparisons and element movements. Comparisons between complex objects, long strings, or user-defined values may have substantial costs of their own.

Adaptivity is more informative than the worst-case bound alone. If an input consists of a small number of long runs, much less work may be required than for a highly disordered input of the same size. However, the number of runs is not the only relevant factor: their lengths, their arrangement, and the overlap between their value ranges also influence performance.

The algorithm's space complexity is a practical limitation. Applications with strict memory limits may prefer an algorithm with smaller auxiliary storage, even if it sacrifices stability or adaptivity.

History and adoption

Tim Peters introduced Timsort into Python 2.3, replacing its earlier sorting implementation. The design emphasized patterns encountered in practical data rather than only uniformly random permutations.

Java adopted Timsort for object-array sorting in Java 7. This does not imply that every Java sorting operation uses it: primitive-array sorting has used different algorithms, and parallel sorting has separate implementation strategies.

Timsort also became an important example in research on formal verification. Work reported in 2015 identified a flaw in the reasoning behind pending-run stack bounds in widely used implementations. Specially constructed run sequences could exceed the assumed capacity of a fixed-size stack.

This was an implementation and invariant-maintenance problem, not evidence that stable natural merging is inherently unsound. Different implementations addressed the issue through changes to stack sizing, merge-collapse rules, or both. The episode demonstrated that an intuitively plausible invariant must actually be maintained by the code before conclusions derived from it are valid.

Comparison with other sorting algorithms

Compared with conventional merge sort, Timsort adds natural-run detection, short-run extension, galloping, and adaptive merge scheduling. Both can provide stability and O(nlog⁡n)O(n\log n) worst-case time, but Timsort can benefit much more from existing order.

Compared with quicksort, Timsort offers stability and a worst-case O(nlog⁡n)O(n\log n) guarantee without depending on pivot selection. Quicksort implementations often use less auxiliary memory and can be faster for particular data types or workloads. Their precise guarantees depend on the variant.

Compared with heapsort, Timsort uses more auxiliary space but preserves equal-key order and exploits natural runs. Heapsort offers an O(nlog⁡n)O(n\log n) worst-case bound with constant auxiliary storage, but is not ordinarily stable.

Compared with insertion sort alone, Timsort retains the latter's usefulness on short or nearly ordered sequences while avoiding quadratic worst-case behavior over the entire input.

Limitations and implementation requirements

Timsort's guarantees depend on a consistent comparison relation. A comparison function that violates ordering requirements—for example, by producing contradictory results for the same elements—can invalidate assumptions used during run detection and merging.

Implementing Timsort correctly is substantially more involved than implementing a basic merge sort. Important details include:

  • preserving stability during run reversal, insertion, and both merge directions;
  • maintaining the full set of required pending-run conditions;
  • handling galloping boundaries and equal keys consistently;
  • sizing temporary storage and stack structures safely;
  • avoiding invalid index calculations and integer overflow.

Its performance advantage is workload-dependent. Inputs with little exploitable order, inexpensive comparisons, or severe memory constraints may favor other algorithms. Timsort is particularly suited to general-purpose stable sorting where pre-existing order is common and comparisons are not necessarily cheap.