Tim Sort is the sort algorithm running inside Python's list.sort() and sorted(), Java's Arrays.sort(Object[]) and Collections.sort(), V8's Array.prototype.sort() (since Node 11), Android's standard library, and Swift's Array.sort(). If you have ever called a "sort" function in those languages on object arrays, you have used Tim Sort.

It was designed by Tim Peters in 2002 specifically for Python's needs: stable, fast on real-world (often partially sorted) data, in-place where reasonable, and graceful on adversarial inputs. The algorithm is a hybrid of merge sort and insertion sort with a long list of practical optimizations that exploit pre-existing order in the input.

The core insight that drives the algorithm: real-world arrays are rarely random. They contain runs (already-sorted subsequences), and a sort algorithm that detects and merges runs instead of starting from scratch does less work.

This chapter explains the algorithm, the run-detection and merging machinery, why it is stable and adaptive, and a simplified educational implementation. Production implementations (Python's listsort.c, JDK's TimSort.java) run to around 1000 lines and build on the simplified version below.

Two algorithms dominate sorting:

For programming languages that sort generic objects (Java, Python, JavaScript, Swift), stability matters. When users sort a list of records by one field and then re-sort by another, they expect the original order to break ties from the second sort. Quick Sort destroys that.

Merge Sort gives stability, but it does too much work on data that is already partially sorted. Real-world examples of partially sorted data:

Tim Sort takes Merge Sort's structure and adds two ideas: detect runs that are already sorted, and merge runs using a small stack with bounded depth invariants.

Tim Sort combines four ideas:

Each of these is worth understanding on its own.

Runs

A natural run is a maximal contiguous subsequence that is either non-decreasing (a <= b <= c <= ...) or strictly decreasing (a > b > c > ...). Tim Sort uses the strictly-decreasing convention for descending runs so that reversal is stable (no equal elements get reordered).

If a descending run is found, it is reversed in place to make it ascending. After this step every run is ascending.

For the array [5, 4, 3, 6, 7, 10, 9, 8, 11]:

After run detection: four ascending runs, ready to be merged.

Minimum Run Length

Very short runs trigger many small merges, which is expensive. Tim Sort fixes a minrun value (typically between 32 and 64) and extends any run shorter than minrun using insertion sort.

The choice of minrun matters. The original Python implementation picks minrun so that n / minrun is just below or equal to a power of 2. This balances the merge tree.

For n = 1000, compute_minrun(1000) = 32. For n = 1_000_000, compute_minrun(1_000_000) ~= 61.

Insertion Sort for Short Runs

Insertion sort is O(n^2) on random data but O(n) on nearly-sorted data, with very low constants. For runs shorter than minrun, the insertion-sort extension is faster than recursive merge work.

Tim Sort uses a binary-search variant of insertion sort: to insert a new element into the already-sorted prefix, find the insertion position with binary search (O(log k)) and then shift elements (O(k)). The binary search saves a constant factor on average inputs.

Merge Stack with Invariants

After run detection and extension, runs are pushed onto a stack as they are produced. Tim Sort maintains two invariants over the top three runs on the stack, denoted A, B, C from bottom to top:

If either invariant is violated, the middle run is merged with its smaller neighbor. The merges happen eagerly as new runs are pushed, keeping the stack short (O(log n) runs) and the merges balanced.

This invariant pair was the source of a bug found in 2015. Researchers at TU Munich showed that the original invariant set was insufficient to bound the stack size, and constructed an adversarial input that caused a stack overflow in Java's TimSort. The fix was to tighten the invariants, which Python adopted as well.

Galloping Mode

The standard "compare and pick the smaller" merge is optimal when the two runs are similar in size. When one run dominates (its elements are mostly smaller, so it "wins" most comparisons), repeated one-element copies are wasteful.

Galloping mode activates when the same run has won MIN_GALLOP comparisons in a row (Python's default is 7). Instead of comparing one element at a time, Tim Sort uses exponential search to find how far the winning run extends, then binary search within the located range, and copies that block in one batch. The combination of exponential plus binary search bounds the work at O(log k) comparisons for a block of size k, far better than the O(k) of one-at-a-time merging when one side dominates.

Galloping makes the algorithm fast on inputs like "two pre-sorted halves concatenated" because almost every comparison is won by the smaller half, and exponential search jumps over large chunks at a time.

The outer loop alternates between extracting one run from the input and possibly merging top-of-stack runs to maintain invariants. When the input is exhausted, the algorithm enters its final phase: merge whatever remains on the stack to produce the sorted result.

A complete production Tim Sort runs to several hundred lines. The educational version below covers run detection, insertion-sort extension, the merge stack with invariants, and the standard merge, but omits galloping mode for clarity. With galloping omitted, the algorithm is still O(n log n) worst case and stable, slightly slower on pre-sorted inputs.

The implementation captures the structure: detect runs, extend short ones with insertion sort, push onto a stack, merge eagerly to maintain invariants, and force-merge at the end. Production code adds galloping, careful memory reuse for the auxiliary array, and additional fast paths.

Worst case O(n log n). The merge structure is the same as Merge Sort: every element is involved in at most O(log n) merges. Insertion sort on minrun-sized chunks is O(minrun^2) per chunk, summed to O(n * minrun), which is O(n) for fixed minrun. Together: O(n log n).

Best case O(n). On already-sorted input, the algorithm finds one giant run, performs no merges, and returns. The total work is the O(n) scan to detect the run.

Adaptive on partially-sorted input. Real-world inputs with k already-sorted runs of average length n / k cost about O(n log k) instead of O(n log n). This is the practical advantage that motivates Tim Sort.

The merge step uses strict less-than (arr[j] < left[i]) to decide which side wins ties. Strict less-than means that when two elements are equal, the left side wins, which preserves the original relative order. This is what makes Tim Sort a stable sort.

Stability matters when sorting objects by a key that is not a primary key. Sorting a list of records by "name" and then by "department" should place all records with the same department together while preserving the within-department alphabetical order from the first sort. Quick Sort cannot do this without a tiebreaker; Tim Sort does it natively.

Languages that sort primitive integer arrays often use Quick Sort or Radix Sort instead. The reason: Quick Sort's instability does not matter for raw integers (no tiebreaker is needed), and its cache locality wins. Tim Sort wins when stability matters and the data is partially sorted, which is the common case for object arrays.

Adaptive means "faster on partially sorted input than the worst case suggests." Among mainstream O(n log n) algorithms, Tim Sort is the one that combines stability with strong adaptiveness, which is why it is the default sort in several languages.

Using strict greater-than in the merge. Stability requires that ties go to the left side: if (arr[j] < left[i]). Replacing < with <= reverses ties and breaks stability.

Choosing minrun poorly. A fixed minrun of 32 is fine for most inputs, but Python's adaptive calculation gives better merge balance on inputs of unusual sizes. For an educational implementation, 32 is acceptable.

Skipping the descending-run reversal. If a descending run is treated as ascending, the run-detection step ends after two elements and the algorithm degenerates. Always reverse strict descending runs before pushing.

Confusing strict and non-strict in run detection. Descending runs must be strict (<) so that reversal does not swap equal elements (which would break stability). Ascending runs use non-strict (<=).

Implementing merge invariants incompletely. The 2015 Java TimSort bug came from invariants that did not guarantee bounded stack depth. Educational implementations can use a simpler invariant (always merge the top two runs eagerly) at the cost of slightly more merging work. Production implementations need the full invariant set described in the Python documentation.