Timsort natural runs and galloping: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Detect natural runs, extend short runs, maintain classic corrected run-stack invariants, and merge stably with exponential/binary galloping after seven consecutive wins.

Detect nondecreasing or strictly decreasing runs, reverse decreasing runs safely, and extend short runs with stable insertion sort. Merge adjacent runs according to classic corrected length invariants. After seven consecutive wins, gallop with exponential and binary search to copy a block.

Open the 3D visualization

Timsort natural runs and galloping example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Timsort natural runs and galloping

Teaching stable adaptive sorting that exploits existing order and long winning blocks during merging.

Choosing an alternative

Plain mergesort ignores natural runs. Introsort is not stable and relies on partitioning rather than run merging. This teaching variant uses classic TimSort scheduling with a fixed gallop threshold, rather than modern CPython Powersort scheduling or adaptive minGallop.

Worked example: input and state changes

Example input

32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Detect runs; minrun 32. Equal values retain increasing original indices.

    State at this checkpoint
    {
      "values": [
        32,
        33,
        34,
        35,
        36,
        37,
        38,
        39,
        40,
        41,
        42,
        43,
        44,
        45,
        46,
        47,
        48,
        49,
        50,
        51,
        52,
        53,
        54,
        55,
        56,
        57,
        58,
        59,
        60,
        61,
        62,
        63,
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11,
        12,
        13,
        14,
        15,
        16,
        17,
        18,
        19,
        20,
        21,
        22,
        23,
        24,
        25,
        26,
        27,
        28,
        29,
        30,
        31
      ],
      "active": [],
      "result": 64,
      "originalIndices": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11,
        12,
        13,
        14,
        15,
        16,
        17,
        18,
        19,
        20,
        21,
        22,
        23,
        24,
        25,
        26,
        27,
        28,
        29,
        30,
        31,
        32,
        33,
        34,
        35,
        36,
        37,
        38,
        39,
        40,
        41,
        42,
        43,
        44,
        45,
        46,
        47,
        48,
        49,
        50,
        51,
        52,
        53,
        54,
        55,
        56,
        57,
        58,
        59,
        60,
        61,
        62,
        63
      ],
      "itemLabels": [
        "origin 0",
        "origin 1",
        "origin 2",
        "origin 3",
        "origin 4",
        "origin 5",
        "origin 6",
        "origin 7",
        "origin 8",
        "origin 9",
        "origin 10",
        "origin 11",
        "origin 12",
        "origin 13",
        "origin 14",
        "origin 15",
        "origin 16",
        "origin 17",
        "origin 18",
        "origin 19",
        "origin 20",
        "origin 21",
        "origin 22",
        "origin 23",
        "origin 24",
        "origin 25",
        "origin 26",
        "origin 27",
        "origin 28",
        "origin 29",
        "origin 30",
        "origin 31",
        "origin 32",
        "origin 33",
        "origin 34",
        "origin 35",
        "origin 36",
        "origin 37",
        "origin 38",
        "origin 39",
        "origin 40",
        "origin 41",
        "origin 42",
        "origin 43",
        "origin 44",
        "origin 45",
        "origin 46",
        "origin 47",
        "origin 48",
        "origin 49",
        "origin 50",
        "origin 51",
        "origin 52",
        "origin 53",
        "origin 54",
        "origin 55",
        "origin 56",
        "origin 57",
        "origin 58",
        "origin 59",
        "origin 60",
        "origin 61",
        "origin 62",
        "origin 63"
      ],
      "stats": [
        0,
        0,
        0,
        32,
        0
      ]
    }
  2. Step 3: Stable merge of adjacent runs 32 and 32.

    State at this checkpoint
    {
      "values": [
        32,
        33,
        34,
        35,
        36,
        37,
        38,
        39,
        40,
        41,
        42,
        43,
        44,
        45,
        46,
        47,
        48,
        49,
        50,
        51,
        52,
        53,
        54,
        55,
        56,
        57,
        58,
        59,
        60,
        61,
        62,
        63,
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11,
        12,
        13,
        14,
        15,
        16,
        17,
        18,
        19,
        20,
        21,
        22,
        23,
        24,
        25,
        26,
        27,
        28,
        29,
        30,
        31
      ],
      "active": [],
      "result": 64,
      "originalIndices": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11,
        12,
        13,
        14,
        15,
        16,
        17,
        18,
        19,
        20,
        21,
        22,
        23,
        24,
        25,
        26,
        27,
        28,
        29,
        30,
        31,
        32,
        33,
        34,
        35,
        36,
        37,
        38,
        39,
        40,
        41,
        42,
        43,
        44,
        45,
        46,
        47,
        48,
        49,
        50,
        51,
        52,
        53,
        54,
        55,
        56,
        57,
        58,
        59,
        60,
        61,
        62,
        63
      ],
      "itemLabels": [
        "origin 0",
        "origin 1",
        "origin 2",
        "origin 3",
        "origin 4",
        "origin 5",
        "origin 6",
        "origin 7",
        "origin 8",
        "origin 9",
        "origin 10",
        "origin 11",
        "origin 12",
        "origin 13",
        "origin 14",
        "origin 15",
        "origin 16",
        "origin 17",
        "origin 18",
        "origin 19",
        "origin 20",
        "origin 21",
        "origin 22",
        "origin 23",
        "origin 24",
        "origin 25",
        "origin 26",
        "origin 27",
        "origin 28",
        "origin 29",
        "origin 30",
        "origin 31",
        "origin 32",
        "origin 33",
        "origin 34",
        "origin 35",
        "origin 36",
        "origin 37",
        "origin 38",
        "origin 39",
        "origin 40",
        "origin 41",
        "origin 42",
        "origin 43",
        "origin 44",
        "origin 45",
        "origin 46",
        "origin 47",
        "origin 48",
        "origin 49",
        "origin 50",
        "origin 51",
        "origin 52",
        "origin 53",
        "origin 54",
        "origin 55",
        "origin 56",
        "origin 57",
        "origin 58",
        "origin 59",
        "origin 60",
        "origin 61",
        "origin 62",
        "origin 63"
      ],
      "stats": [
        2,
        1,
        0,
        32,
        2
      ]
    }
  3. Step 7: Take the smaller front item; equal keys come from the left run.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3,
        36,
        37,
        38,
        39,
        40,
        41,
        42,
        43,
        44,
        45,
        46,
        47,
        48,
        49,
        50,
        51,
        52,
        53,
        54,
        55,
        56,
        57,
        58,
        59,
        60,
        61,
        62,
        63,
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11,
        12,
        13,
        14,
        15,
        16,
        17,
        18,
        19,
        20,
        21,
        22,
        23,
        24,
        25,
        26,
        27,
        28,
        29,
        30,
        31
      ],
      "active": [
        3
      ],
      "result": 64,
      "originalIndices": [
        32,
        33,
        34,
        35,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11,
        12,
        13,
        14,
        15,
        16,
        17,
        18,
        19,
        20,
        21,
        22,
        23,
        24,
        25,
        26,
        27,
        28,
        29,
        30,
        31,
        32,
        33,
        34,
        35,
        36,
        37,
        38,
        39,
        40,
        41,
        42,
        43,
        44,
        45,
        46,
        47,
        48,
        49,
        50,
        51,
        52,
        53,
        54,
        55,
        56,
        57,
        58,
        59,
        60,
        61,
        62,
        63
      ],
      "itemLabels": [
        "origin 32",
        "origin 33",
        "origin 34",
        "origin 35",
        "origin 4",
        "origin 5",
        "origin 6",
        "origin 7",
        "origin 8",
        "origin 9",
        "origin 10",
        "origin 11",
        "origin 12",
        "origin 13",
        "origin 14",
        "origin 15",
        "origin 16",
        "origin 17",
        "origin 18",
        "origin 19",
        "origin 20",
        "origin 21",
        "origin 22",
        "origin 23",
        "origin 24",
        "origin 25",
        "origin 26",
        "origin 27",
        "origin 28",
        "origin 29",
        "origin 30",
        "origin 31",
        "origin 32",
        "origin 33",
        "origin 34",
        "origin 35",
        "origin 36",
        "origin 37",
        "origin 38",
        "origin 39",
        "origin 40",
        "origin 41",
        "origin 42",
        "origin 43",
        "origin 44",
        "origin 45",
        "origin 46",
        "origin 47",
        "origin 48",
        "origin 49",
        "origin 50",
        "origin 51",
        "origin 52",
        "origin 53",
        "origin 54",
        "origin 55",
        "origin 56",
        "origin 57",
        "origin 58",
        "origin 59",
        "origin 60",
        "origin 61",
        "origin 62",
        "origin 63"
      ],
      "stats": [
        2,
        1,
        0,
        32,
        2
      ]
    }
  4. Step 10: Take the smaller front item; equal keys come from the left run.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        39,
        40,
        41,
        42,
        43,
        44,
        45,
        46,
        47,
        48,
        49,
        50,
        51,
        52,
        53,
        54,
        55,
        56,
        57,
        58,
        59,
        60,
        61,
        62,
        63,
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11,
        12,
        13,
        14,
        15,
        16,
        17,
        18,
        19,
        20,
        21,
        22,
        23,
        24,
        25,
        26,
        27,
        28,
        29,
        30,
        31
      ],
      "active": [
        6
      ],
      "result": 64,
      "originalIndices": [
        32,
        33,
        34,
        35,
        36,
        37,
        38,
        7,
        8,
        9,
        10,
        11,
        12,
        13,
        14,
        15,
        16,
        17,
        18,
        19,
        20,
        21,
        22,
        23,
        24,
        25,
        26,
        27,
        28,
        29,
        30,
        31,
        32,
        33,
        34,
        35,
        36,
        37,
        38,
        39,
        40,
        41,
        42,
        43,
        44,
        45,
        46,
        47,
        48,
        49,
        50,
        51,
        52,
        53,
        54,
        55,
        56,
        57,
        58,
        59,
        60,
        61,
        62,
        63
      ],
      "itemLabels": [
        "origin 32",
        "origin 33",
        "origin 34",
        "origin 35",
        "origin 36",
        "origin 37",
        "origin 38",
        "origin 7",
        "origin 8",
        "origin 9",
        "origin 10",
        "origin 11",
        "origin 12",
        "origin 13",
        "origin 14",
        "origin 15",
        "origin 16",
        "origin 17",
        "origin 18",
        "origin 19",
        "origin 20",
        "origin 21",
        "origin 22",
        "origin 23",
        "origin 24",
        "origin 25",
        "origin 26",
        "origin 27",
        "origin 28",
        "origin 29",
        "origin 30",
        "origin 31",
        "origin 32",
        "origin 33",
        "origin 34",
        "origin 35",
        "origin 36",
        "origin 37",
        "origin 38",
        "origin 39",
        "origin 40",
        "origin 41",
        "origin 42",
        "origin 43",
        "origin 44",
        "origin 45",
        "origin 46",
        "origin 47",
        "origin 48",
        "origin 49",
        "origin 50",
        "origin 51",
        "origin 52",
        "origin 53",
        "origin 54",
        "origin 55",
        "origin 56",
        "origin 57",
        "origin 58",
        "origin 59",
        "origin 60",
        "origin 61",
        "origin 62",
        "origin 63"
      ],
      "stats": [
        2,
        1,
        0,
        32,
        2
      ]
    }
  5. Step 13: Stable sort complete: runs 2, merges 1, galloped blocks 1.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11,
        12,
        13,
        14,
        15,
        16,
        17,
        18,
        19,
        20,
        21,
        22,
        23,
        24,
        25,
        26,
        27,
        28,
        29,
        30,
        31,
        32,
        33,
        34,
        35,
        36,
        37,
        38,
        39,
        40,
        41,
        42,
        43,
        44,
        45,
        46,
        47,
        48,
        49,
        50,
        51,
        52,
        53,
        54,
        55,
        56,
        57,
        58,
        59,
        60,
        61,
        62,
        63
      ],
      "active": [],
      "result": 64,
      "originalIndices": [
        32,
        33,
        34,
        35,
        36,
        37,
        38,
        39,
        40,
        41,
        42,
        43,
        44,
        45,
        46,
        47,
        48,
        49,
        50,
        51,
        52,
        53,
        54,
        55,
        56,
        57,
        58,
        59,
        60,
        61,
        62,
        63,
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11,
        12,
        13,
        14,
        15,
        16,
        17,
        18,
        19,
        20,
        21,
        22,
        23,
        24,
        25,
        26,
        27,
        28,
        29,
        30,
        31
      ],
      "itemLabels": [
        "origin 32",
        "origin 33",
        "origin 34",
        "origin 35",
        "origin 36",
        "origin 37",
        "origin 38",
        "origin 39",
        "origin 40",
        "origin 41",
        "origin 42",
        "origin 43",
        "origin 44",
        "origin 45",
        "origin 46",
        "origin 47",
        "origin 48",
        "origin 49",
        "origin 50",
        "origin 51",
        "origin 52",
        "origin 53",
        "origin 54",
        "origin 55",
        "origin 56",
        "origin 57",
        "origin 58",
        "origin 59",
        "origin 60",
        "origin 61",
        "origin 62",
        "origin 63",
        "origin 0",
        "origin 1",
        "origin 2",
        "origin 3",
        "origin 4",
        "origin 5",
        "origin 6",
        "origin 7",
        "origin 8",
        "origin 9",
        "origin 10",
        "origin 11",
        "origin 12",
        "origin 13",
        "origin 14",
        "origin 15",
        "origin 16",
        "origin 17",
        "origin 18",
        "origin 19",
        "origin 20",
        "origin 21",
        "origin 22",
        "origin 23",
        "origin 24",
        "origin 25",
        "origin 26",
        "origin 27",
        "origin 28",
        "origin 29",
        "origin 30",
        "origin 31"
      ],
      "stats": [
        2,
        1,
        1,
        32,
        2
      ]
    }

Expected final state

Stable sort complete: runs 2, merges 1, galloped blocks 1.

Complexity and input bounds

Family: Sorting. Time complexity: O(n log n) worst case; O(n) sorted input.

Implementation detail: Up to 256 values retain original-index labels so stability is visible in WebGL and 2D. Downloads sort values in place and output stable original indices followed by run, merge, galloped-block, minrun and peak-stack counters. Tests include hand-checked left/right gallop counts and a four-run stack, in every language. Standard minrun is used; production merge-memory optimizations are omitted.

Space complexity: O(n) auxiliary values/original-index buffers and O(log n) active run stack, plus recorded frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

1..256 values 0..99. Labels retain original indices to demonstrate stability. Standard minrun; classic stack policy, fixed gallop threshold 7.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Descending runs must be strictly decreasing so reversal cannot reorder equal keys. Equal merge keys come from the left run. Left and right gallops need different equal-key bounds. Restore both three-run and four-run stack conditions.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Stable Timsort teaching variant, n 0..256 values 0..99, sorts a in place and returns n (-1 for invalid n). Output capacity at least n+5: first n entries are original indices in sorted order, then [runs found/extended, merges, nonempty galloped blocks, minrun, peak run-stack size]. Strictly decreasing runs are reversed; short runs use stable insertion extension. Standard minrun reduction to 32..64 for large inputs; corrected classic three/four-run collapse conditions. Merges use stable left <= right and exponential/binary galloping after a fixed seven consecutive wins. Does not implement adaptive minGallop or modern CPython Powersort scheduling. O(n log n) worst-case time, O(n) auxiliary storage; sorted input is O(n). Empty input writes five zeros. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(a, n, output) {
    if (n < 0 || n > 256) { return -1; }
    for (let i = 0; i < n+5; i++) { output[i] = 0; }
    let ids = Array(256).fill(0); let temp = Array(256).fill(0); let tempIDs = Array(256).fill(0); let starts = Array(256).fill(0); let lengths = Array(256).fill(0); let reduced = n; let discarded = 0; let minrun = 0; let position = 0; let runEnd = 0; let forcedEnd = 0; let left = 0; let right = 0; let swapValue = 0; let swapID = 0; let key = 0; let keyID = 0; let cursor = 0; let stack = 0; let force = 0; let at = 0; let low = 0; let mid = 0; let high = 0; let write = 0; let winsL = 0; let winsR = 0; let offset = 0; let lower = 0; let upper = 0; let probe = 0;
    for (let i = 0; i < n; i++) { ids[i] = i; }
    while (reduced >= 64) { discarded = discarded | (reduced & 1); reduced = reduced >> 1; }
    minrun = reduced+discarded; output[n+3] = minrun;
    while (position < n || stack > 1) { force = 0;
     if (position < n) { runEnd = position+1;
      if (runEnd < n && a[runEnd] < a[position]) { while (runEnd < n && a[runEnd] < a[runEnd-1]) { runEnd++; } left = position; right = runEnd-1; while (left < right) { swapValue = a[left]; a[left] = a[right]; a[right] = swapValue; swapID = ids[left]; ids[left] = ids[right]; ids[right] = swapID; left++; right--; } }
      else { while (runEnd < n && a[runEnd] >= a[runEnd-1]) { runEnd++; } }
      forcedEnd = position+minrun; if (forcedEnd > n) { forcedEnd = n; }
      for (let i = runEnd; i < forcedEnd; i++) { key = a[i]; keyID = ids[i]; cursor = i-1; while (cursor >= position && a[cursor] > key) { a[cursor+1] = a[cursor]; ids[cursor+1] = ids[cursor]; cursor--; } a[cursor+1] = key; ids[cursor+1] = keyID; }
      if (runEnd < forcedEnd) { runEnd = forcedEnd; } starts[stack] = position; lengths[stack] = runEnd-position; stack++; output[n]++; if (stack > output[n+4]) { output[n+4] = stack; } position = runEnd;
     } else { force = 1; }
     while (stack > 1) { at = stack-2;
      if (force == 0) { if ((at > 0 && lengths[at-1] <= lengths[at]+lengths[at+1]) || (at > 1 && lengths[at-2] <= lengths[at-1]+lengths[at])) { if (lengths[at-1] < lengths[at+1]) { at--; } } else { if (lengths[at] > lengths[at+1]) { break; } } }
      else { if (at > 0 && lengths[at-1] < lengths[at+1]) { at--; } }
      low = starts[at]; mid = low+lengths[at]; high = mid+lengths[at+1];
      for (let i = low; i < high; i++) { temp[i] = a[i]; tempIDs[i] = ids[i]; }
      left = low; right = mid; write = low; winsL = 0; winsR = 0; output[n+1]++;
      while (left < mid && right < high) {
       if (temp[left] <= temp[right]) { a[write] = temp[left]; ids[write] = tempIDs[left]; left++; winsL++; winsR = 0; } else { a[write] = temp[right]; ids[write] = tempIDs[right]; right++; winsR++; winsL = 0; } write++;
       if (winsL >= 7 && left < mid && right < high) { offset = 1; lower = left; while (left+offset < mid && temp[left+offset] <= temp[right]) { offset = offset << 1; } upper = left+offset+1; if (upper > mid) { upper = mid; } while (lower < upper) { probe = (lower+upper) >> 1; if (temp[probe] <= temp[right]) { lower = probe+1; } else { upper = probe; } } if (lower > left) { output[n+2]++; } while (left < lower) { a[write] = temp[left]; ids[write] = tempIDs[left]; write++; left++; } winsL = 0; }
       if (winsR >= 7 && left < mid && right < high) { offset = 1; lower = right; while (right+offset < high && temp[right+offset] < temp[left]) { offset = offset << 1; } upper = right+offset+1; if (upper > high) { upper = high; } while (lower < upper) { probe = (lower+upper) >> 1; if (temp[probe] < temp[left]) { lower = probe+1; } else { upper = probe; } } if (lower > right) { output[n+2]++; } while (right < lower) { a[write] = temp[right]; ids[write] = tempIDs[right]; write++; right++; } winsR = 0; }
      }
      while (left < mid) { a[write] = temp[left]; ids[write] = tempIDs[left]; write++; left++; }
      while (right < high) { a[write] = temp[right]; ids[write] = tempIDs[right]; write++; right++; }
      lengths[at] += lengths[at+1]; for (let i = at+1; i < stack-1; i++) { starts[i] = starts[i+1]; lengths[i] = lengths[i+1]; } stack--;
     }
    }
    for (let i = 0; i < n; i++) { output[i] = ids[i]; }
    return n;
}

Source

Original-author design notes in a fixed CPython 3.10 snapshot, not a journal-paper attribution. The bounded teaching variant uses corrected classic run-stack collapse and a fixed seven-win gallop trigger, omitting adaptive minGallop and later Powersort scheduling.