cf.completefrontend
SORTING · ADVANCED

TimSort

Find the already sorted stretches (runs) in the list, extend short runs with insertion sort, then merge the runs.

Time O(n log n)Space O(n)3 practice problemsStep-through picture

The idea

TimSort is the sort behind Array.prototype.sort in V8 (Chrome, Node.js, Deno) since 2018, and behind Python's sorted. It was designed by Tim Peters for real-world data, which is often partly sorted already.

It walks the list looking for runs: stretches that already go up (or strictly go down, which it reverses). Short runs are grown to a minimum length, called minRun, using insertion sort, which is fast on short pieces. Then it merges the runs together, like merge sort, until one run covers the whole list.

Because it reuses existing order, TimSort sorts an already sorted list in O(n) and never does worse than O(n log n). It is also stable, which the JavaScript spec has required of sort since ES2019.

An everyday example

Combining partly sorted stacks of mail

A clerk receives mail that is mostly in date order already, in stretches. She walks along the pile and splits it wherever the dates stop going up, setting each stretch aside as a stack. A stretch that runs backwards she just flips over. Very short stacks she tops up with a few more letters, slotting each one into place by hand. Then she merges stacks two at a time, always taking the earlier date from the top, until one stack is left.

How the example maps to the code
In the exampleIn the code
A stretch already in date orderA run: items[start..end-1]
Flipping a backwards stretchReversing a strictly descending run
Topping up a short stack by handInsertion sort up to start + minRun
Merging two stacksMerging neighboring runs [from, mid) and [mid, to)

From the slow way to timsort

  1. Merge sort splits a list at fixed midpoints, no matter what is in it. But real data is rarely random. Lists are often mostly sorted, sorted with a few new items at the end, or made of sorted pieces glued together. Merge sort spends O(n log n) on them anyway.
  2. So start by looking at the data. Walk from the left and find the longest stretch that is already going up, called a run. A stretch going strictly down is just as good: reverse it and it goes up. A sorted list is one run. Then merge runs instead of halves, and order already in the data is never redone.
  3. Random data has a problem: its runs are tiny, often 2 items, and merging thousands of tiny runs wastes time. So set a minimum run length, minRun. If a natural run is shorter, extend it to minRun items with insertion sort, which is very fast on short lists.
  4. Finally, merge the runs together, two at a time, until one run covers the list, taking from the left run on ties so equal items keep their order. Find runs, grow short ones with insertion sort, and merge them stably: that is TimSort, in a simplified form.

How it works

  1. Start at start = 0. Find the run there: extend end while items keep going up (>=). If the run starts by going strictly down, extend while it keeps going strictly down and then reverse it.
  2. If the run is shorter than minRun, extend it to start + minRun (or the end of the list) by insertion-sorting the extra items into it.
  3. Record the run as [start, stop] and continue from stop until the whole list is split into sorted runs.
  4. Merge neighboring runs in pairs: copy the left run, then merge it with the right run back into the array.
  5. Repeat the pairwise merging until only one run is left: the list is sorted.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function timSort(items, minRun = 32) {
  2. let runs = [];
  3. let start = 0;
  4. while (start < items.length) {
  5. let end = start + 1;
  6. if (end < items.length && items[end] < items[start]) {
  7. while (end < items.length && items[end] < items[end - 1]) end++;
  8. items.splice(start, end - start, ...items.slice(start, end).reverse());
  9. } else {
  10. while (end < items.length && items[end] >= items[end - 1]) end++;
  11. }
  12. const stop = Math.min(items.length, Math.max(end, start + minRun));
  13. for (let i = end; i < stop; i++) {
  14. const current = items[i];
  15. let j = i - 1;
  16. while (j >= start && items[j] > current) items[j + 1] = items[j--];
  17. items[j + 1] = current;
  18. }
  19. runs.push([start, stop]);
  20. start = stop;
  21. }
  22. while (runs.length > 1) {
  23. const next = [];
  24. for (let r = 0; r + 1 < runs.length; r += 2) {
  25. const [from, mid] = runs[r];
  26. const to = runs[r + 1][1];
  27. const left = items.slice(from, mid);
  28. let i = 0;
  29. let j = mid;
  30. for (let k = from; k < to; k++) {
  31. if (j >= to || (i < left.length && left[i] <= items[j])) items[k] = left[i++];
  32. else items[k] = items[j++];
  33. }
  34. next.push([from, to]);
  35. }
  36. if (runs.length % 2 === 1) next.push(runs[runs.length - 1]);
  37. runs = next;
  38. }
  39. return items;
  40. }

How fast it is

TimeO(n log n)
Extra memoryO(n)

Finding and growing runs is O(n × minRun), which is linear because minRun is a small constant. Each merge round touches every item once, and there are log of the number of runs rounds. The merge copies a run into a buffer.

  • Best caseO(n)

    An already sorted list like [1, 2, 3, 4, 5], or a strictly descending one: it is one run, found with about n comparisons, and there is nothing to merge.

  • Average caseO(n log n)

    Random data has short runs, so it becomes about n / minRun runs of insertion sort and log of that many merge rounds.

  • Worst caseO(n log n)

    No input is worse than random data: growing runs costs at most O(n × minRun) and merging is merge sort on runs.

Common mistakes

  • Reversing descending runs that contain equal items. That breaks stability. Only reverse strictly descending runs.
  • Using < instead of <= when merging, which also breaks stability.
  • Thinking minRun must be tiny. Real TimSort picks 32 to 64 so that the number of runs is close to a power of two, which keeps merges balanced.
  • Assuming every engine uses TimSort. The spec only requires a stable sort; V8 uses TimSort, but other engines may use other stable algorithms such as merge sort.

When to use it

Look for these clues in a problem:

  • You are asked how JavaScript's built-in sort works, or why it is stable.
  • The data is likely partly sorted, such as a list re-sorted after a few changes or logs from several ordered sources.
  • The question is about runs: finding stretches that are already in order, or merging them.

Check yourself

Answer each one in your head first, then open it.

How many comparisons does this TimSort make on an already sorted list of 1,000 items?

1,000. One comparison decides that the run goes up, then the run-finding loop compares each of the 999 later items with the one before it. It finds a single run, so there is nothing to merge.

Why does TimSort use insertion sort for short runs instead of splitting further?

For a few dozen items, insertion sort's simple loop is faster than the overhead of more merging, and it is stable. Growing runs to minRun also limits how many merges are needed.

Why must runs be merged with their neighbors and not, say, the first with the third?

Merging non-neighbors would move items of the third run ahead of equal items in the second run, which breaks stability, and the merged result wouldn't be one contiguous stretch.

What happens to the last run when the list ends before start + minRun?

stop is capped at items.length, so the last run is simply shorter than minRun. It is still sorted, so it is merged like any other.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The run-finding loop keeps this rule: every pair in runs covers a sorted stretch, the stretches sit side by side, and together they cover items[0..start-1]. Each step adds one sorted stretch starting at start: an ascending run is sorted as found, a strictly descending run is sorted after reversing, and the insertion sort that grows a run to stop keeps it sorted, just as insertion sort always does.

Each step moves start forward to stop, which is at least start + 1, so the loop ends with runs covering the whole list. Each merge round combines neighboring sorted runs into one sorted run, by the same argument as merge sort's merge. The number of runs roughly halves each round, so the merge loop ends with one run, which is the whole sorted list.

Stability needs care in three places, and the code handles all three. Only strictly descending runs are reversed, so no equal items flip. Insertion sort stops at an equal item (items[j] > current). The merge takes from the left run when items are equal (left[i] <= items[j]). Because runs are always merged with their neighbors, items from an earlier run are always on the left.

Going deeper

3 more ideas

Why reverse only strictly descending runs

Reversing a run flips the order of equal items. If a descending run could contain equal items, like [5, 3, 3, 1], reversing it would swap the two 3s and break stability. So TimSort only reverses runs that go strictly down, where no two items are equal. Ascending runs may contain equal items, because they are kept as they are.

What the real TimSort adds

This template keeps the core ideas but simplifies the rest. The real algorithm computes minRun from the length (between 32 and 64), uses binary insertion sort, and merges runs as it finds them, using a stack with rules that keep merges balanced. During a merge, if one run keeps winning many times in a row, it switches to galloping: it jumps ahead by 1, 3, 7, 15, ... places to find how far it can copy in one block, then binary searches inside that jump.

How long it takes

Finding runs is one pass. If the list is already sorted, there is one run and nothing to merge: O(n). In the worst case there are about n / minRun runs, and merging them pairwise takes log of that many rounds of O(n) work: O(n log n). The merge needs a buffer the size of the smaller run, so space is O(n).

Work it by hand

Every step in a table, with why

Sort 11 numbers with minRun = 3. The list has an ascending run, a descending run, a short run to grow, and a one-item tail.

items = [3, 6, 8, 11, 9, 5, 2, 10, 4, 7, 1], minRun = 3

StepStepRangeitemsrunsWhat happensWhy
1Find runstart = 0, end = 4[3, 6, 8, 11, 9, 5, 2, 10, 4, 7, 1][0, 4]Ascending run of 46 < 3 is false, so the run goes up. It extends while each item is >= the one before, and stops at 9. Its length 4 is already at least minRun.
2Find runstart = 4, end = 7[3, 6, 8, 11, 9, 5, 2, 10, 4, 7, 1][0, 4]Strictly descending: 9, 5, 25 < 9, so this run goes down. It extends while each item is strictly smaller, and stops at 10.
3Reversestart = 4, end = 7[3, 6, 8, 11, 2, 5, 9, 10, 4, 7, 1][0, 4], [4, 7]Now 2, 5, 9The splice reverses it in place. It had no equal items, so reversing can't break stability. Its length is 3, so stop = 7, nothing grows, and [4, 7] is recorded.
4Find runstart = 7, end = 9[3, 6, 8, 11, 2, 5, 9, 4, 10, 7, 1][0, 4], [4, 7]Descending 10, 4, reversedA run of only 2. stop = Math.min(11, Math.max(9, 7 + 3)) = 10, so it must grow by one item.
5Growi = 9[3, 6, 8, 11, 2, 5, 9, 4, 7, 10, 1][0, 4], [4, 7], [7, 10]Insert 7 into the runInsertion sort shifts 10 right and puts 7 at index 8. The run 4, 7, 10 is recorded.
6Find runstart = 10, end = 11[3, 6, 8, 11, 2, 5, 9, 4, 7, 10, 1]4 runs, last [10, 11]One item leftstop would be 13, but Math.min caps it at 11, the end of the list. A short last run is allowed.
7Merge[0, 4) with [4, 7)[2, 3, 5, 6, 8, 9, 11, 4, 7, 10, 1]-First pair of runsCopy the left run into left, then merge it with 2, 5, 9 back into indexes 0 to 6.
8Merge[7, 10) with [10, 11)[2, 3, 5, 6, 8, 9, 11, 1, 4, 7, 10][0, 7], [7, 11]Second pair of runs1 comes from the right run before all three left items. The round ends with 2 runs.
9Merge[0, 7) with [7, 11)[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11][0, 11]One run left: stopruns.length is 1, so the merge loop ends.

It returns [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]. It found 4 runs, reversed 2 of them, grew 1 with a single insertion, and needed 2 rounds of merging.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
TimSortO(n log n)O(n)General-purpose stable sorting of real data, which is often partly sorted. It is what Array.prototype.sort uses in V8.
Merge sortO(n log n)O(n)You want a short, stable sort to write by hand, and the data is random, so finding runs would not help.
Insertion sortO(n²)O(1)Lists of a few dozen items. TimSort uses it for exactly that.
Quick sortO(n log n)O(log n)Stability isn't needed and the data is random numbers, where in-place partitioning is faster.

Extra memory: O(n): each merge copies the left run into left, and runs holds up to n / minRun pairs. The real TimSort copies only the smaller run, but it is still O(n) in the worst case.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for TimSort and the other approaches, on a scale where each line up is 10 times more steps.
  • TimSort, Merge sort, Quick sort O(n log n)
  • Insertion sort O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
TimSort339,96620 million
Merge sort339,96620 million
Insertion sort1001 million1 trillion
Quick sort339,96620 million

Inputs that need care

5 tricky inputs
An empty list
start < items.length is false at once, runs stays empty, and the merge loop needs more than one run, so the list is returned as it is.
Strictly descending: [9, 8, 7, 6, 5, 4]
It is one run. It is reversed in place in a single step, and there is nothing to merge: O(n).
All equal: [4, 4, 4, 4]
The ascending check uses >=, so the whole list is one run. Nothing is reversed or merged, and equal items keep their order.
A descending stretch with a tie: [5, 3, 3, 1]
The descending run stops at the second 3, because 3 < 3 is false. Only 5, 3 is reversed, then the second 3 is inserted after the first. The result [1, 3, 3, 5] keeps the two 3s in order.
Data sorted, then a few new items appended
One long run, then a short stretch at the end. The stretch is grown into a run with insertion sort and merged in, close to O(n) when only a few items were added. This is common in real apps, like adding items to a sorted feed.

Variations and follow-ups

Twists interviewers add

Galloping merges

When one run wins many comparisons in a row (7 in the real TimSort), it is likely to keep winning. The merge then jumps ahead 1, 3, 7, 15, ... places to find where the streak ends, binary-searches inside that jump, and copies the whole block at once. Merging a run that fits entirely before another takes about log comparisons instead of one per item.

A stack of runs

The real algorithm doesn't collect all runs first. It pushes each run on a stack and merges the top runs whenever their lengths break two rules: each run must be longer than the one above it, and longer than the two above it together. This keeps merges balanced and the stack short.

Computing minRun

The real minRun is between 32 and 64, chosen so that the list length divided by minRun is a power of 2 or just under. Then the runs pair up evenly in the merges. Lists shorter than 64 are sorted with binary insertion sort alone.

Powersort

A newer way to decide which runs to merge, based on where each run would sit in a balanced merge tree. Python switched its list sort from TimSort's merge rules to Powersort's in version 3.11.

In an interview

Spot it, explain it, answer follow-ups
  • TimSort comes up when someone asks "what does sort() actually do?" or "why is sorting an already sorted array so fast?". The answer is runs: sorted data is one run, found in one pass.
  • Explain it as three steps: find natural runs (reversing strictly descending ones), grow short runs to minRun with insertion sort, and merge runs stably. Then name its two big guarantees: O(n) on sorted input, O(n log n) always.
  • Test by hand with an ascending run followed by a descending run, as in the trace. Check that a descending stretch with equal items is not reversed as a whole.
  • A common follow-up is "why does it reverse only strictly descending runs?". Reversing a run with equal items would put those items in the opposite order, which breaks stability.

Where frontend code uses it

The same idea in real UI code
  • V8's Array.prototype.sort, used in Chrome, Edge, Node.js, and Deno, has been TimSort since V8 7.0 (2018). Before that it used quick sort and was not stable.
  • Because the spec requires sort to be stable (since ES2019), sorting a table by one column and then another keeps ties in the order of the earlier sort.
  • Re-sorting a list after a small change (a new message, an edited row) is fast with the built-in sort, because most of the list is one long run.

Related algorithms