Introsort visualised: quick sort with a heap fallback

Step 1 of 111

Comparisons 0
Swaps 0
sorted indices 0

420

171

882

634

295

746

127

508

359

9110

2111

compare
swap
sorted

Pseudocode

 1  maxDepth = 2 * floor(log2(n))
 2  introsort(0, n - 1, maxDepth)
 3  
 4  introsort(lo, hi, depth):
 5    if lo >= hi: return
 6    if hi - lo < 16:
 7      insertionSort(lo, hi); return
 8    if depth == 0:
 9      heapsort(lo, hi); return
10    p = partition(lo, hi)
11    introsort(lo, p - 1, depth - 1)
12    introsort(p + 1, hi, depth - 1)
13  
14  insertionSort(lo, hi):
15    for i from lo + 1 to hi
16      key = a[i]; j = i - 1
17      while j >= lo and a[j] > key
18        a[j + 1] = a[j]; j = j - 1
19      a[j + 1] = key
20  
21  partition(lo, hi):
22    pivot = a[hi]; i = lo - 1
23    for j from lo to hi - 1
24      if a[j] <= pivot: i++; swap a[i], a[j]
25    swap a[i + 1], a[hi]
26    return i + 1
27  
28  heapsort(lo, hi):
29    size = hi - lo + 1
30    for k from size/2 - 1 downto 0: heapify(lo, hi, lo + k)
31    for end from hi downto lo + 1
32      swap a[lo], a[end]; heapify(lo, end - 1, lo)
33  
34  heapify(lo, hi, root):
35    r = root - lo; l = 2r + 1; rr = 2r + 2; largest = root
36    if l < size and a[lo+l] > a[largest]: largest = lo + l
37    if rr < size and a[lo+rr] > a[largest]: largest = lo + rr
38    if largest != root:
39      swap a[root], a[largest]; heapify(lo, hi, largest)

Step log

1maxDepth = 2 * floor(log2(12)) = 6Line 1

How it works, runtime and memory

Introsort (Introspective Sort) fixes the pathological worst case of Quick Sort, which can degrade to O(n²) for unfortunate pivots. It starts with regular Quick Sort but watches the recursion depth. Once depth exceeds 2 · ⌊log₂(n)⌋, the algorithm switches to Heap Sort, which guarantees O(n log n). Very small sub-arrays (typically ≤ 16 elements) are finished with Insertion Sort which is very fast on small inputs. This combines the average-case speed of Quick Sort, the worst-case O(n log n) guarantee of Heap Sort and the constant-factor advantage of Insertion Sort on small ranges. Memory is O(log n) for the recursion stack and the algorithm is not stable.

Complexity

Best case: O(n log n)
Average case: O(n log n)
Worst case: O(n log n)
Extra space: O(log n)

When to use it

Standard sort algorithm in the C++ STL (std::sort) since C++11. First choice when a generic, fast in-place sort with guaranteed O(n log n) worst case is needed.