IntroSort: Mechanism, Complexity Analysis & Interactive Visualizer

Introsort

A hybrid sorting algorithm: starts with Quick Sort for high speed, switches to Heap Sort if recursion limits are hit, and drops to Insertion Sort for tiny subarrays.

How it works

Introsort (Introductory Sort), designed by David Musser in 1997, is the standard sort algorithm in the C++ Standard Template Library (STL). It provides the best of both worlds—Quicksort's speed and Heapsort's worst-case guarantees—using three phases:

1. Quicksort Phase: Begin sorting using Quicksort. It partitions subarrays recursively by choosing pivots (typically median-of-three).
2. Heapsort Switch: Keep track of recursion depth. If the depth exceeds a threshold (typically 2 · log₂(n)), the partition is likely pathological (e.g. nested duplicate patterns). Switch that partition to Heapsort to ensure O(n log n) worst-case behavior.
3. Insertion Sort Cleanup: When any subarray size drops below a threshold (usually 16 elements), skip partitioning and sort it quickly using Insertion Sort.

Complexity

Interactive visualization

Pseudocode

procedure introsort(A):
  n ← length(A)
  maxDepth ← 2 * floor(log2(n))
  introsortUtil(A, 0, n - 1, maxDepth)

procedure introsortUtil(A, left, right, depthLimit):
  size ← right - left + 1
  if size < 16:
    insertionSort(A, left, right)
  else if depthLimit == 0:
    heapsort(A, left, right)
  else:
    p ← partition(A, left, right)
    introsortUtil(A, left, p - 1, depthLimit - 1)
    introsortUtil(A, p + 1, right, depthLimit - 1)

JavaScript implementation

function introsort(arr) {
  const n = arr.length;
  const maxDepth = 2 * Math.floor(Math.log2(n || 1));
  
  function insertionSort(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--;
      }
      arr[j + 1] = key;
    }
  }
  
  function heapsort(left, right) {
    const size = right - left + 1;
    function heapify(hSize, i) {
      let largest = i;
      const l = 2 * i + 1;
      const r = 2 * i + 2;
      if (l < hSize && arr[left + l] > arr[left + largest]) largest = l;
      if (r < hSize && arr[left + r] > arr[left + largest]) largest = r;
      if (largest !== i) {
        [arr[left + i], arr[left + largest]] = [arr[left + largest], arr[left + i]];
        heapify(hSize, largest);
      }
    }
    for (let i = Math.floor(size / 2) - 1; i >= 0; i--) heapify(size, i);
    for (let i = size - 1; i > 0; i--) {
      [arr[left], arr[left + i]] = [arr[left + i], arr[left]];
      heapify(i, 0);
    }
  }
  
  function partition(left, right) {
    const pivotVal = arr[right];
    let i = left - 1;
    for (let j = left; j < right; j++) {
      if (arr[j] < pivotVal) {
        i++;
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
    return i + 1;
  }
  
  function introsortLimit(left, right, depthLimit) {
    const size = right - left + 1;
    if (size < 16) {
      insertionSort(left, right);
      return;
    }
    if (depthLimit === 0) {
      heapsort(left, right);
      return;
    }
    const p = partition(left, right);
    introsortLimit(left, p - 1, depthLimit - 1);
    introsortLimit(p + 1, right, depthLimit - 1);
  }
  
  introsortLimit(0, n - 1, maxDepth);
  return arr;
}

Pros and cons

When (not) to use it

• Standard in-place sort: Excellent default sort when stability is not a requirement (e.g. C++ vector sorting).
• Strictly stable sorting: Avoid when duplicate stability is essential; use Timsort or Merge Sort instead.