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

Intro Sort

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

Input Data

Visualization

Visual representation of the data structure

About Intro Sort

A hybrid sorting algorithm that provides both fast average performance and optimal worst-case performance. It starts with quicksort, switches to heapsort when the recursion depth exceeds a level based on the number of elements being sorted, and switches to insertion sort for small partitions.

Code Editor

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

function introSort(arr) {
  let maxdepth = Math.floor(Math.log2(arr.length)) * 2;
  introsort_helper(arr, 0, arr.length - 1, maxdepth);
  return arr;
}

function introsort_helper(arr, begin, end, maxdepth) {
  if (end - begin < 16) {
    insertionSort(arr, begin, end);
    return;
  }
  if (maxdepth === 0) {
    heapSort(arr, begin, end);
    return;
  }
  let p = partition(arr, begin, end);
  introsort_helper(arr, begin, p - 1, maxdepth - 1);
  introsort_helper(arr, p + 1, end, maxdepth - 1);
}

function partition(arr, begin, end) {
  let pivot = arr[end];
  let i = begin - 1;
  for (let j = begin; j < end; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[end]] = [arr[end], arr[i + 1]];
  return i + 1;
}

function heapSort(arr, begin, end) {
  let n = end - begin + 1;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i, begin);
  }
  for (let i = n - 1; i > 0; i--) {
    [arr[begin], arr[begin + i]] = [arr[begin + i], arr[begin]];
    heapify(arr, i, 0, begin);
  }
}

function heapify(arr, n, i, offset) {
  let largest = i;
  let l = 2 * i + 1;
  let r = 2 * i + 2;
  if (l < n && arr[offset + l] > arr[offset + largest]) largest = l;
  if (r < n && arr[offset + r] > arr[offset + largest]) largest = r;
  if (largest !== i) {
    [arr[offset+i], arr[offset+largest]] = [arr[offset+largest], arr[offset+i]];
    heapify(arr, n, largest, offset);
  }
}

function insertionSort(arr, left, right) {
  for (let i = left + 1; i <= right; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= left && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}

Variable State

{
  "arr": "[2,1,0,5,8,3,7,4,9,6]"
}

Intro Sort: How It Works

Last updated October 28, 2026

Overview

Intro Sort (introspective sort) starts as Quick Sort but watches its own recursion depth. If the depth passes 2 * floor(log2(n)), the input is behaving like a Quick Sort worst case, so it switches that range to Heap Sort, which is guaranteed O(n log n). Small ranges, under 16 elements, are finished with Insertion Sort.

This combination gives Quick Sort's speed on typical data, Heap Sort's worst-case guarantee, and Insertion Sort's low overhead on tiny pieces. It is the algorithm behind std::sort in most C++ standard libraries and behind .NET's Array.Sort.

The default input has 10 elements, below the 16-element threshold, so the dry run goes straight to Insertion Sort — a nice illustration that hybrid sorts often never use their 'main' algorithm on small inputs. Try 20 or more numbers to see partitioning, and a sorted 40-element list to push it toward the heap-sort fallback.

Step by step

Compute maxdepth = 2 * floor(log2(n)).
If the current range has fewer than 16 elements, sort it with Insertion Sort and return.
If maxdepth has reached 0, sort the range with Heap Sort and return.
Otherwise partition around a pivot as in Quick Sort.
Recurse on both sides with maxdepth - 1.

Complexity

Case	Cost	Why
Best case	O(n log n)	Balanced partitions, as in Quick Sort.
Average case	O(n log n)	Quick Sort behaviour dominates.
Worst case	O(n log n)	The depth limit hands bad ranges to Heap Sort.
Extra space	O(log n)	Recursion depth is capped at 2·log2(n).

When to use it

General-purpose unstable sorting where worst-case guarantees matter, e.g. sorting untrusted input that could be crafted to attack Quick Sort.
Systems code in C and C++ — it is the default choice there.
Any time you would use Quick Sort but cannot rule out adversarial or pre-sorted data.

Common mistakes

It is not stable; use Merge Sort or Tim Sort when equal keys must keep their order.
Getting the depth limit wrong either never triggers the fallback or triggers it too often.
The 16-element cutoff is a tuning constant; benchmarking on your platform may suggest a different value.

Worked Example: Intro 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 Intro Sort: follow each row, predict the next one, and compare. The run below takes 80 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: 2, 1, 0, 5, 8, 3, 7, 4, 9, 6
Result: return value = [0,1,2,3,4,5,6,7,8,9], arr = [0,1,2,3,4,5,6,7,8,9]

Step	Line	Array	What happens
1	1	[2, 1, 0, 5, 8, 3, 7, 4, 9, 6]
4	9	[2, 1, 0, 5, 8, 3, 7, 4, 9, 6]	status = Switching to Insertion Sort
5	68	[2, 1, 0, 5, 8, 3, 7, 4, 9, 6]	begin = 0, end = 9, status = Running Insertion Sort
9	72	[2, 1, 0, 5, 8, 3, 7, 4, 9, 6]	j = 0, key = 1, condition = 2 > 1
10	73	[2, 2, 0, 5, 8, 3, 7, 4, 9, 6]
12	76	[1, 2, 0, 5, 8, 3, 7, 4, 9, 6]
16	72	[1, 2, 0, 5, 8, 3, 7, 4, 9, 6]	j = 1, key = 0, condition = 2 > 0
17	73	[1, 2, 2, 5, 8, 3, 7, 4, 9, 6]
19	72	[1, 2, 2, 5, 8, 3, 7, 4, 9, 6]	j = 0, key = 0, condition = 1 > 0
20	73	[1, 1, 2, 5, 8, 3, 7, 4, 9, 6]
22	76	[0, 1, 2, 5, 8, 3, 7, 4, 9, 6]
34	72	[0, 1, 2, 5, 8, 3, 7, 4, 9, 6]	j = 4, key = 3, condition = 8 > 3
35	73	[0, 1, 2, 5, 8, 8, 7, 4, 9, 6]
37	72	[0, 1, 2, 5, 8, 8, 7, 4, 9, 6]	j = 3, key = 3, condition = 5 > 3
38	73	[0, 1, 2, 5, 5, 8, 7, 4, 9, 6]
40	76	[0, 1, 2, 3, 5, 8, 7, 4, 9, 6]
44	72	[0, 1, 2, 3, 5, 8, 7, 4, 9, 6]	j = 5, key = 7, condition = 8 > 7
45	73	[0, 1, 2, 3, 5, 8, 8, 4, 9, 6]
47	76	[0, 1, 2, 3, 5, 7, 8, 4, 9, 6]
51	72	[0, 1, 2, 3, 5, 7, 8, 4, 9, 6]	j = 6, key = 4, condition = 8 > 4
52	73	[0, 1, 2, 3, 5, 7, 8, 8, 9, 6]
54	72	[0, 1, 2, 3, 5, 7, 8, 8, 9, 6]	j = 5, key = 4, condition = 7 > 4
55	73	[0, 1, 2, 3, 5, 7, 7, 8, 9, 6]
57	72	[0, 1, 2, 3, 5, 7, 7, 8, 9, 6]	j = 4, key = 4, condition = 5 > 4
58	73	[0, 1, 2, 3, 5, 5, 7, 8, 9, 6]
60	76	[0, 1, 2, 3, 4, 5, 7, 8, 9, 6]
68	72	[0, 1, 2, 3, 4, 5, 7, 8, 9, 6]	j = 8, key = 6, condition = 9 > 6
69	73	[0, 1, 2, 3, 4, 5, 7, 8, 9, 9]
71	72	[0, 1, 2, 3, 4, 5, 7, 8, 9, 9]	j = 7, key = 6, condition = 8 > 6
72	73	[0, 1, 2, 3, 4, 5, 7, 8, 8, 9]
74	72	[0, 1, 2, 3, 4, 5, 7, 8, 8, 9]	j = 6, key = 6, condition = 7 > 6
75	73	[0, 1, 2, 3, 4, 5, 7, 7, 8, 9]
77	76	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
80	4	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]	return value = [0,1,2,3,4,5,6,7,8,9]

Frequently Asked Questions

About IntroSort (Introspective Sort)

What is IntroSort?

IntroSort (Introspective Sort) is a hybrid sorting algorithm that provides both fast average performance and an optimal O(n log n) worst-case performance. It starts with Quick Sort but switches to Heap Sort when the recursion depth exceeds a certain level, and finally switches to Insertion Sort for very small partitions.

Why does IntroSort switch algorithms?

It switches algorithms to combine their strengths and mitigate their weaknesses. It uses Quick Sort for its excellent average-case speed. It switches to Heap Sort to avoid Quick Sort's O(n^2) worst-case scenario. It uses Insertion Sort for small partitions because its low overhead makes it faster for tiny arrays.

What is the time complexity of IntroSort?

The time complexity is O(n log n) in all cases (best, average, and worst). This makes it a very reliable and high-performance general-purpose sorting algorithm, and it is the default sorting algorithm in many C++ standard libraries.

Is IntroSort stable?

No, because its primary component, Quick Sort, and its fallback, Heap Sort, are not stable algorithms, IntroSort is also not stable. It does not preserve the relative order of equal elements.

What triggers the switch to Heap Sort?

The switch to Heap Sort is triggered when the recursion depth of Quick Sort reaches a certain limit. This limit is typically set to 2 * log2(n). This 'introspection' prevents the Quick Sort part of the algorithm from degrading to its O(n^2) worst-case performance on pathological inputs.

What triggers the switch to Insertion Sort?

IntroSort switches to Insertion Sort when the size of the partition to be sorted becomes very small (e.g., 16 elements or fewer). For such small arrays, the overhead of recursion in Quick Sort or Heap Sort is higher than the straightforward loops of Insertion Sort.

What is the space complexity of IntroSort?

The space complexity is O(log n) due to the recursion stack depth required by Quick Sort and Heap Sort.

How does IntroSort compare to Tim Sort?

Both are advanced hybrid sorts. IntroSort is generally faster on average for random data but is not stable. Tim Sort is stable and is exceptionally fast on data with pre-existing sorted runs, which is common in real-world scenarios. The choice depends on whether stability is required and the expected nature of the data.

Is IntroSort an in-place sort?

Yes, it is considered an in-place sorting algorithm as it does not require auxiliary storage proportional to the input size, only the O(log n) space for the recursion stack.

Why is it called 'Introspective' Sort?

It is named 'Introspective' because the algorithm 'watches' its own performance during the Quick Sort phase. If the recursion becomes too deep (an indicator of a potential worst-case scenario), it reflects on this and switches its strategy to Heap Sort to guarantee O(n log n) performance.

Where can I learn more?

You can find a more detailed explanation on GeeksforGeeks.