Introsort with heap fallback: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Use median-of-three, three-way quicksort until the depth budget runs out; heap-sort remaining large ranges and insertion-sort ranges of at most eight elements.

Partition large ranges around a median-of-three pivot, keeping equal keys together. Decrease the allowed partition depth; when it reaches zero, heap-sort the remaining large range. Finish short ranges with insertion sort.

Open the 3D visualization

Introsort with heap fallback example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Introsort with heap fallback

Teaching a fast quicksort hybrid with a worst-case fallback rather than relying on favorable pivot splits.

Choosing an alternative

Ordinary quicksort can repeatedly make poor splits. Introsort limits the damage by switching to heapsort; this bounded version also has an explicit insertion cutoff of eight.

Worked example: input and state changes

Example input

38,12,65,8,43,27,91,19,4,32,76,50 | -1

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: Median-of-three pivot; insertion cutoff 8; heap fallback at zero remaining depth.

    State at this checkpoint
    {
      "values": [
        38,
        12,
        65,
        8,
        43,
        27,
        91,
        19,
        4,
        32,
        76,
        50
      ],
      "active": [],
      "result": 12,
      "output": [
        0,
        0,
        0
      ]
    }
  2. Step 10: Swap positions 4 and 5.

    State at this checkpoint
    {
      "values": [
        12,
        32,
        8,
        4,
        27,
        38,
        91,
        19,
        43,
        76,
        50,
        65
      ],
      "active": [
        4,
        5
      ],
      "result": 12,
      "output": [
        1,
        0,
        0
      ]
    }
  3. Step 20: Shift a larger item right.

    State at this checkpoint
    {
      "values": [
        8,
        12,
        12,
        32,
        27,
        19,
        38,
        91,
        43,
        76,
        50,
        65
      ],
      "active": [
        1,
        2
      ],
      "result": 12,
      "output": [
        1,
        0,
        1
      ]
    }
  4. Step 29: Shift a larger item right.

    State at this checkpoint
    {
      "values": [
        4,
        8,
        12,
        19,
        27,
        32,
        38,
        91,
        91,
        76,
        50,
        65
      ],
      "active": [
        7,
        8
      ],
      "result": 12,
      "output": [
        1,
        0,
        2
      ]
    }
  5. Step 39: Sorted. Counters: partitions 1, heap fallbacks 0, insertion runs 2.

    State at this checkpoint
    {
      "values": [
        4,
        8,
        12,
        19,
        27,
        32,
        38,
        43,
        50,
        65,
        76,
        91
      ],
      "active": [],
      "result": 12,
      "output": [
        1,
        0,
        2
      ]
    }

Expected final state

Sorted. Counters: partitions 1, heap fallbacks 0, insertion runs 2.

Complexity and input bounds

Family: Sorting. Time complexity: O(n log n) worst-case default.

Implementation detail: At most 64 values; default depth is twice floor(log2(n)). An override from zero through twelve makes the fallback testable. Ranges of eight or fewer always use insertion sort. Downloads return n and write three counters: partitions, heap fallbacks and insertion runs. Tests force a heap fallback rather than relying on a chance bad pivot.

Space complexity: O(log n) active traversal state with fixed portable scratch buffers; the Python implementation recurses. Saved frames add space.

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..64 values 0..99 | optional depth limit -1 (automatic) or 0..12. Zero forces heap fallback for ranges longer than eight.

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

The depth limit belongs to each subrange. Preserve the subrange offset inside heap operations. A three-way equal partition prevents duplicate keys from producing unnecessary recursive work. This sort is not stable.

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
// Sort a in place, n 0..64 values 0..99. depthLimit -1 means 2*floor(log2(n)); overrides 0..12 allow fallback testing. Three-way partition around median of first/middle/last values; insertion sort for range length <=8; heap sort for larger ranges at zero remaining depth. Returns n, or -1 for invalid depth override. Output capacity at least 3, counters [partitions, heap fallbacks, insertion runs]; empty/singleton inputs have zero counters. Not stable. O(n log n) worst-case default, O(log n) active traversal state; fixed portable scratch arrays and recursive Python. 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, depthLimit, output) {
    output[0] = 0; output[1] = 0; output[2] = 0;
    if (depthLimit < -1 || depthLimit > 12) { return -1; }
    if (n < 2) { return n; }
    let limit = depthLimit; let value = n; if (limit == -1) { limit = 0; while (value > 1) { limit += 2; value = value >> 1; } }
    let stackLow = Array(256).fill(0); let stackHigh = Array(256).fill(0); let stackDepth = Array(256).fill(0); let top = 1; let low = 0; let high = n-1; let depth = 0; let length = 0; let key = 0; let cursor = 0; let temp = 0; let root = 0; let child = 0; let heapSize = 0; let mid = 0; let x = 0; let y = 0; let z = 0; let pivot = 0; let lt = 0; let gt = 0;
    stackHigh[0] = n-1; stackDepth[0] = limit;
    while (top > 0) { top--; low = stackLow[top]; high = stackHigh[top]; depth = stackDepth[top]; length = high-low+1;
     if (length <= 8) { output[2]++; for (let position = low+1; position <= high; position++) { key = a[position]; cursor = position-1; while (cursor >= low && a[cursor] > key) { a[cursor+1] = a[cursor]; cursor--; } a[cursor+1] = key; } }
     else { if (depth == 0) { output[1]++; heapSize = length; for (let start = (length >> 1)-1; start >= 0; start--) { root = start; while (2*root+1 < heapSize) { child = 2*root+1; if (child+1 < heapSize && a[low+child+1] > a[low+child]) { child++; } if (a[low+root] >= a[low+child]) { break; } temp = a[low+root]; a[low+root] = a[low+child]; a[low+child] = temp; root = child; } } for (let end = length-1; end > 0; end--) { temp = a[low]; a[low] = a[low+end]; a[low+end] = temp; root = 0; heapSize = end; while (2*root+1 < heapSize) { child = 2*root+1; if (child+1 < heapSize && a[low+child+1] > a[low+child]) { child++; } if (a[low+root] >= a[low+child]) { break; } temp = a[low+root]; a[low+root] = a[low+child]; a[low+child] = temp; root = child; } } }
     else { output[0]++; mid = (low+high) >> 1; x = a[low]; y = a[mid]; z = a[high]; pivot = x; if ((x <= y && y <= z) || (z <= y && y <= x)) { pivot = y; } else { if ((y <= z && z <= x) || (x <= z && z <= y)) { pivot = z; } }
     lt = low; cursor = low; gt = high; while (cursor <= gt) { if (a[cursor] < pivot) { temp = a[lt]; a[lt] = a[cursor]; a[cursor] = temp; lt++; cursor++; } else { if (a[cursor] > pivot) { temp = a[cursor]; a[cursor] = a[gt]; a[gt] = temp; gt--; } else { cursor++; } } }
     if (gt+1 < high) { stackLow[top] = gt+1; stackHigh[top] = high; stackDepth[top] = depth-1; top++; }
     if (low < lt-1) { stackLow[top] = low; stackHigh[top] = lt-1; stackDepth[top] = depth-1; top++; }
     } }
    }
    return n;
}

Source

Original introspective sorting research. The bounded playground makes its median-of-three pivot, three-way partition, insertion cutoff and depth override explicit; it is not a claim to reproduce the paper exact STL implementation.