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.
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.
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 ] }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 ] }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 ] }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 ] }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:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
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.
- Introspective Sorting and Selection Algorithms
David R. Musser (1997). Original introsort research paper.