TimSort

TimSort is the sort behind Python's sorted() and list.sort(), Java's Arrays.sort for objects, Android, V8's Array.prototype.sort and Swift. Tim Peters designed it in 2002 around one observation: real data is rarely random. Logs are mostly in time order, a list that was sorted yesterday has had a few items appended, a table is sorted by one column and you now want another. TimSort finds the order that is already there and does as little work as possible on top of it.

It is a merge sort at heart, plus four ideas: natural runs, minrun with binary insertion sort, a run stack with balancing rules, and galloping merges. Use the dropdowns to choose the array size (20–60) and how ordered it starts, press Sort, and each idea shows up in turn.

Input 3 5 8 9 12, 11 10 7 2, 14 1, 6 13: run A is ascending, run B is strictly descending and gets reversed to 2 7 10 11, run C is too short and is extended to minrun 4 by binary insertion to 1 6 13 14. B is not longer than C so B and C merge; then A is not longer than BC so they merge into 1 to 14 sorted
TimSort turns existing order into runs, fixes reversed or short runs, and merges runs only when the stack rules say their sizes are similar.

A note on the constants

Real TimSort uses a minrun of 32 to 64 (CPython sets MIN_MERGE to 64, Java to 32). Any array under 64 values is then sorted with binary insertion sort alone, with no runs to merge. It also switches to galloping only after 7 wins in a row. To make all of TimSort visible on 20–60 values, this page scales both down: minrun 4–8 and galloping after 3 wins. Everything else is the real algorithm, including Java's corrected stack rule.

1. Natural runs

From the current position, TimSort scans for the longest stretch that is already in order: ascending (each value ≥ the one before) or strictly descending. A descending run is reversed in place. It has to be strictly descending, or reversing it would reorder equal values and break stability. Finding a run of length k costs k − 1 comparisons, and the run is then already sorted. On an already-sorted array the whole array is one run: n − 1 comparisons and nothing else. Merge sort would still make about n log₂ n / 2.

2. minrun and binary insertion sort

A run that is too short would create lots of tiny, expensive merges. So when a natural run is shorter than minrun, TimSort extends it to minrun values with binary insertion sort: each new value is placed by binary search in the sorted part, and the values after that spot shift right one place. On a handful of values this is very fast, because the shifts are one cheap block move.

minrun is chosen from n so that n / minrun is a power of two or just below one. Take the top bits of n, and add 1 if any lower bit is set. That keeps the final merges balanced, the way merge sort's halving does.

computeMinRun(n):          # here MIN_MERGE = 8; CPython 64, Java 32
    r = 0
    while n >= MIN_MERGE:
        r |= n & 1
        n >>= 1
    return n + r           # 40 -> 5,  60 -> 8,  25 -> 7

3. The run stack

Each run is pushed onto a stack. On this page the stack is the row of brackets under the array: runs sit side by side in the array, so the bottom of the stack is the leftmost bracket and the top is the rightmost. After every push, TimSort checks two rules on the top runs, X (top), Y and Z:

Y > X            each run is longer than the one above it
Z > Y + X        and longer than the two above it together

While a rule is broken, it merges Y with whichever neighbour is smaller: X, or Z if Z < X. When the rules hold, run lengths grow at least like Fibonacci numbers down the stack. So the stack never holds more than about logφ n runs, and every merge joins runs of similar size, which is what keeps TimSort O(n log n).

The original version checked only the top three runs. In 2015 researchers proving TimSort correct with the KeY verifier found that this can leave the rule broken deeper in the stack, and that on specially crafted inputs Java's fixed-size stack could overflow. The fix, used here, also checks W > Z + Y for the run below Z.

4. Merging, with a small buffer

Before merging runs A and B, TimSort trims what is already in place. Values at the start of A that are ≤ B's first value are already in position, and so are values at the end of B that are ≥ A's last value. Only the middle is merged. Then it copies the shorter of the two into a temp buffer. If that is A, it merges left to right into A's old slots; if it is B, right to left into B's. The extra memory is min(|A|, |B|) cells, at most n / 2, and usually much less on partly ordered data. Gray bars in the array are slots whose value has moved out and not yet been refilled.

5. Galloping

A normal merge compares one pair per output value. But if one run keeps winning, say the next 30 values of A all come before B's next value, those 30 comparisons are wasted. After minGallop wins in a row, TimSort switches to galloping. It checks positions 1, 3, 7, 15, … ahead until it overshoots, then binary-searches the last gap. It finds a stretch of k values in about 2 log₂ k comparisons and copies it as one block.

Galloping in run A = 11 14 18 21 25 28 30 33 37 40 42 45 48 52 55 60 with B's next value 50: check positions 1, 3, 7, 15; 60 at 15 overshoots, binary search 8 to 15 finds 52 at 13, so A[0..12] is copied as one block in about 7 comparisons instead of 13
Galloping jumps 1, 3, 7, 15 ahead and binary-searches the last gap, so a long winning streak costs only about 2 log k comparisons.

Galloping costs more than a plain comparison when the stretch turns out short. So TimSort adapts: each successful gallop lowers minGallop by one, and falling back to one-at-a-time raises it by two. On data that comes in clusters it gallops readily; on random data it soon stops trying. The "mode" line on the canvas shows which mode the merge is in.

What to try

  • Already sorted: one run and n − 1 comparisons. The gray bar underneath is merge sort on the same array.
  • Reversed: one strictly descending run (this option uses distinct values), reversed in place for n − 1 comparisons. With equal values the run would stop at each tie, because reversing past one would swap two equal values.
  • Pre-sorted chunks: long natural runs, some reversed, and merges that trim and gallop a lot.
  • Nearly sorted: a few misplaced values. Watch the trims leave most of each run untouched.
  • Random: TimSort's worst kind of input. Every run is extended to minrun by insertion sort, galloping rarely pays, and at this size it makes a few more comparisons than plain merge sort. That is the trade: it gives up a little on random data to win big on ordered data.

Stability

TimSort is stable: equal values keep their original order. Every step preserves it. Runs are only ever reversed when strictly descending, binary insertion places a value after any equal ones, and merges take from the left run on a tie. This is why Python and Java use it for sorting records by one key after another.

Common mistakes

  • Reversing non-strict descending runs. 5 3 3 1 reversed swaps the two 3s, and the sort is no longer stable.
  • Checking only the top three runs. This was the bug in Python, Java and Android until 2015.
  • Galloping from the start. On random data a gallop that finds one value costs more than a plain comparison. That is why TimSort waits for a streak, and why minGallop adapts.
  • Thinking TimSort is always faster than merge sort. On random data it does about the same work, sometimes a little more. Its win is on data with existing order, which is most real data.