Tim Sort Visualizer: Step-by-Step Animation & Complexity

Tim Sort

Category: Sorting | Time: O(n log n) | Space: O(n)

Input Data

Visualization

Visual representation of the data structure

About Tim Sort

A hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python programming language.

Code Editor

The code is for reference. Editing it won't affect the visualization.

const RUN = 32;

// Insertion sort for sub-arrays
function insertionSort(arr, left, right) {
    for (let i = left + 1; i <= right; i++) {
        let temp = arr[i];
        let j = i - 1;
        while (j >= left && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

// Merge function to merge sorted runs
function merge(arr, l, m, r) {
    let len1 = m - l + 1, len2 = r - m;
    let left = new Array(len1);
    let right = new Array(len2);
    for (let i = 0; i < len1; i++)
        left[i] = arr[l + i];
    for (let i = 0; i < len2; i++)
        right[i] = arr[m + 1 + i];

    let i = 0, j = 0, k = l;

    while (i < len1 && j < len2) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }

    while (i < len1) {
        arr[k] = left[i];
        k++;
        i++;
    }

    while (j < len2) {
        arr[k] = right[j];
        k++;
        j++;
    }
}

// Main Tim Sort function
function timSort(arr) {
    let n = arr.length;
    // Sort individual sub-arrays of size RUN
    for (let i = 0; i < n; i += RUN) {
        insertionSort(arr, i, Math.min((i + RUN - 1), (n - 1)));
    }

    // Start merging from size RUN. It will merge
    // to form size 2*RUN, then 4*RUN, 8*RUN and so on
    for (let size = RUN; size < n; size = 2 * size) {
        for (let left = 0; left < n; left += 2 * size) {
            let mid = left + size - 1;
            let right = Math.min((left + 2 * size - 1), (n - 1));
            if(mid < right) {
              merge(arr, left, mid, right);
            }
        }
    }
    return arr;
}

Variable State

{
  "n": 13
}

Tim Sort: How It Works

Last updated October 28, 2026

Overview

Tim Sort is a hybrid of Insertion Sort and Merge Sort, designed by Tim Peters for Python in 2002 and now used by Python, Java (for objects) and many other runtimes. Its idea is that real-world data often contains sorted stretches, so it sorts small chunks quickly and then merges them.

The simplified version on this page splits the array into runs of RUN = 32 elements, sorts each run with Insertion Sort, and then merges runs of size 32, 64, 128 and so on. Production Tim Sort goes further: it detects naturally occurring runs, reverses descending ones, and uses 'galloping' to speed up merges.

The default input has 13 elements, which is smaller than one run. The dry run therefore shows a single Insertion Sort pass and no merging — exactly what real Tim Sort does for small arrays. Paste in more than 32 numbers to see the merge phase.

Step by step

Divide the array into consecutive runs of size RUN (the last run may be shorter).
Sort each run with Insertion Sort.
Set size = RUN and merge neighbouring runs of length size into runs of length 2 * size.
Double size and repeat until one run covers the whole array.

Complexity

Case	Cost	Why
Best case	O(n)	Full Tim Sort detects that already-sorted input is one long run.
Average case	O(n log n)	Insertion sort on fixed-size runs plus log(n/RUN) merge levels.
Worst case	O(n log n)	Merge structure guarantees the bound.
Extra space	O(n)	Temporary arrays during merging.

When to use it

General-purpose stable sorting in standard libraries — you are probably already using it via sorted() in Python or Arrays.sort on objects in Java.
Data with existing order: logs appended in time order, lists that were sorted and then lightly edited.
Whenever stability and a guaranteed O(n log n) are both required.

Common mistakes

The fixed-run version shown here does not get the O(n) best case; that requires natural run detection.
A RUN size that is too large makes the insertion-sort phase quadratic in practice; 32–64 is the usual range.
Merging with < instead of <= loses stability, the property Tim Sort is chosen for.

Worked Example: Tim Sort Dry Run

Generated from the same trace that drives the visualizer above, using the default input.

A dry run is the best way to check your understanding of Tim Sort: follow each row, predict the next one, and compare. The run below takes 170 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.

Input: 5, 21, 7, 23, 19, 1, 45, 67, 89, 3, 0, -1, 50
Result: return value = [-1,0,1,3,5,7,19,21,23,45,50,67,89]

Step	Line	Array	What happens
1	51	[5, 21, 7, 23, 19, 1, 45, 67, 89, 3, 0, -1, 50]	n = 13
11	8	[5, 21, 7, 23, 19, 1, 45, 67, 89, 3, 0, -1, 50]	j = 1, temp = 7, condition = 21 > 7
12	9	[5, 21, 21, 23, 19, 1, 45, 67, 89, 3, 0, -1, 50]
14	12	[5, 7, 21, 23, 19, 1, 45, 67, 89, 3, 0, -1, 50]
22	8	[5, 7, 21, 23, 19, 1, 45, 67, 89, 3, 0, -1, 50]	j = 3, temp = 19, condition = 23 > 19
23	9	[5, 7, 21, 23, 23, 1, 45, 67, 89, 3, 0, -1, 50]
25	8	[5, 7, 21, 23, 23, 1, 45, 67, 89, 3, 0, -1, 50]	j = 2, temp = 19, condition = 21 > 19
26	9	[5, 7, 21, 21, 23, 1, 45, 67, 89, 3, 0, -1, 50]
28	12	[5, 7, 19, 21, 23, 1, 45, 67, 89, 3, 0, -1, 50]
32	8	[5, 7, 19, 21, 23, 1, 45, 67, 89, 3, 0, -1, 50]	j = 4, temp = 1, condition = 23 > 1
33	9	[5, 7, 19, 21, 23, 23, 45, 67, 89, 3, 0, -1, 50]
35	8	[5, 7, 19, 21, 23, 23, 45, 67, 89, 3, 0, -1, 50]	j = 3, temp = 1, condition = 21 > 1
36	9	[5, 7, 19, 21, 21, 23, 45, 67, 89, 3, 0, -1, 50]
38	8	[5, 7, 19, 21, 21, 23, 45, 67, 89, 3, 0, -1, 50]	j = 2, temp = 1, condition = 19 > 1
39	9	[5, 7, 19, 19, 21, 23, 45, 67, 89, 3, 0, -1, 50]
41	8	[5, 7, 19, 19, 21, 23, 45, 67, 89, 3, 0, -1, 50]	j = 1, temp = 1, condition = 7 > 1
42	9	[5, 7, 7, 19, 21, 23, 45, 67, 89, 3, 0, -1, 50]
44	8	[5, 7, 7, 19, 21, 23, 45, 67, 89, 3, 0, -1, 50]	j = 0, temp = 1, condition = 5 > 1
45	9	[5, 5, 7, 19, 21, 23, 45, 67, 89, 3, 0, -1, 50]
47	12	[1, 5, 7, 19, 21, 23, 45, 67, 89, 3, 0, -1, 50]
63	8	[1, 5, 7, 19, 21, 23, 45, 67, 89, 3, 0, -1, 50]	j = 8, temp = 3, condition = 89 > 3
64	9	[1, 5, 7, 19, 21, 23, 45, 67, 89, 89, 0, -1, 50]
66	8	[1, 5, 7, 19, 21, 23, 45, 67, 89, 89, 0, -1, 50]	j = 7, temp = 3, condition = 67 > 3
67	9	[1, 5, 7, 19, 21, 23, 45, 67, 67, 89, 0, -1, 50]
69	8	[1, 5, 7, 19, 21, 23, 45, 67, 67, 89, 0, -1, 50]	j = 6, temp = 3, condition = 45 > 3
70	9	[1, 5, 7, 19, 21, 23, 45, 45, 67, 89, 0, -1, 50]
72	8	[1, 5, 7, 19, 21, 23, 45, 45, 67, 89, 0, -1, 50]	j = 5, temp = 3, condition = 23 > 3
73	9	[1, 5, 7, 19, 21, 23, 23, 45, 67, 89, 0, -1, 50]
75	8	[1, 5, 7, 19, 21, 23, 23, 45, 67, 89, 0, -1, 50]	j = 4, temp = 3, condition = 21 > 3
76	9	[1, 5, 7, 19, 21, 21, 23, 45, 67, 89, 0, -1, 50]
78	8	[1, 5, 7, 19, 21, 21, 23, 45, 67, 89, 0, -1, 50]	j = 3, temp = 3, condition = 19 > 3
79	9	[1, 5, 7, 19, 19, 21, 23, 45, 67, 89, 0, -1, 50]
81	8	[1, 5, 7, 19, 19, 21, 23, 45, 67, 89, 0, -1, 50]	j = 2, temp = 3, condition = 7 > 3
82	9	[1, 5, 7, 7, 19, 21, 23, 45, 67, 89, 0, -1, 50]
84	8	[1, 5, 7, 7, 19, 21, 23, 45, 67, 89, 0, -1, 50]	j = 1, temp = 3, condition = 5 > 3
85	9	[1, 5, 5, 7, 19, 21, 23, 45, 67, 89, 0, -1, 50]
87	12	[1, 3, 5, 7, 19, 21, 23, 45, 67, 89, 0, -1, 50]
91	8	[1, 3, 5, 7, 19, 21, 23, 45, 67, 89, 0, -1, 50]	j = 9, temp = 0, condition = 89 > 0
92	9	[1, 3, 5, 7, 19, 21, 23, 45, 67, 89, 89, -1, 50]
94	8	[1, 3, 5, 7, 19, 21, 23, 45, 67, 89, 89, -1, 50]	j = 8, temp = 0, condition = 67 > 0

The remaining 47 key steps follow the same pattern. Press play in the visualizer to watch every step through to the result.

Frequently Asked Questions

About Tim Sort

What is Tim Sort?

Tim Sort is a highly efficient, adaptive, and stable hybrid sorting algorithm, derived from Merge Sort and Insertion Sort. It is designed to perform well on many kinds of real-world data. It is the standard sorting algorithm in Python and Java (for objects).

How does Tim Sort work?

It works by finding 'natural runs' (contiguous sorted subsequences) in the data. For runs that are smaller than a certain threshold (minrun), it uses Insertion Sort to extend them. Then, it merges these sorted runs using a highly optimized Merge Sort, which employs techniques like 'galloping' to speed up the merge process.

What is the time complexity of Tim Sort?

Tim Sort has a best-case time complexity of O(n) when the input is already sorted. Its average and worst-case time complexity are both O(n log n), making it very efficient and reliable.

Why is Tim Sort so popular in practice?

It's highly efficient because it's adaptive. It takes advantage of the fact that real-world data is often partially sorted with existing 'runs'. Its use of Insertion Sort for small segments and its intelligent merging strategy make it faster than a pure Merge Sort for most practical datasets.

What is a 'minrun' in Tim Sort?

A 'minrun' is a minimum size for a 'run' (a sorted subsequence). In TimSort, if a natural run is shorter than the minrun, it's extended using Insertion Sort until it reaches that minimum size. This helps to ensure that the later merging process is balanced and efficient. The minrun size is calculated based on the size of the total array, typically between 32 and 65.

What is 'galloping' in Tim Sort's merge step?

Galloping is an optimization used during the merge step. When data from one run is consistently winning against the other, the algorithm enters 'galloping mode'. It uses an exponential search (gallop) to quickly find where the next element from the other run should be placed, skipping over large chunks of data.

Is Tim Sort an in-place algorithm?

It is not strictly in-place. It aims to be space-efficient. For the merge step, it requires temporary storage. The size of this temporary space is at most N/2 in the worst case, but often much smaller (e.g., the size of the smaller run being merged).

Why does Tim Sort use Insertion Sort?

Insertion Sort is used because it is extremely fast for small arrays (due to low overhead) and for arrays that are nearly sorted. Both of these conditions are frequently met by the 'runs' that Tim Sort processes.

How does Tim Sort maintain stability?

It maintains stability because both of its component algorithms, Insertion Sort and its specific implementation of Merge Sort, are stable. During the merge, if elements are equal, the element from the run that appeared first in the original array is always chosen first.

Can Tim Sort's performance degrade?

Unlike Quick Sort, Tim Sort does not have a common worst-case input that degrades its performance to O(n^2). Its performance is consistently O(n log n) due to its merge-based strategy. The main performance variations come from how much existing order it can exploit in the input data.

Where can I learn more?

You can find a more detailed explanation on GeeksforGeeks.