Introsort
Quick Sort with a depth limit, falling back to Heap Sort on deep recursion.
- Comparisons 0
- Swaps 0
- sorted indices 0
- 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
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.