DSA Sorting

IntroSort

Question-led: if quicksort is usually fastest on arrays, why does C++ std::sort refuse to trust it alone?

starts like quicksort, watches recursion , and falls back to heapsort for a Theta(n log n) ceiling. Tiny partitions finish with insertion sort. Usually unstable.

Algorithm journey

Partition like quicksort

Chase average-case speed and locality.

Watch depth

Compare recursion depth to ~2 log2 n.

Fall back to heapsort

Guarantee progress when pivots fail.

Finish tiny ranges

Insertion sort cleans small partitions.

What actually happens

Naive idea: plain quicksort everywhere. Fast until an adversary (or unlucky data) squares the cost.

Better idea: introspect. Keep quicksort's common case; buy a worst-case ceiling with heapsort.

It still is typically unstable, and the constants depend on pivot strategy and cutoffs.

Invariant

While in quicksort mode, the usual partition invariant holds; once depth is exceeded, the active range is sorted by heapsort, which restores a sorted segment without relying on further pivots.

How to choose introsort

1. Contiguous arrays, stability optional? Introsort-style hybrids are a strong library default.

2. Need stability? Use TimSort/mergesort instead.

3. Teaching pure algorithms? Study quick/heap/insertion separately, then see why hybrids exist.

Quantitative check

Depth limit ~2 log2(10^7) ≈ 46. A pathological quicksort without a guard can hit ~10^7 levels of work patterns; the heap fallback keeps total work O(n log n).

How it works

Start with Quick Sort

Begin sorting using Quick Sort, which is generally the fastest on average.

Check Recursion Depth

If the recursion depth exceeds a limit (usually 2 * log(n)), switch to Heap Sort. This prevents Quick Sort's worst-case O(n²) scenario.

Use Insertion Sort for Small Chunks

If the partition size becomes small (e.g., fewer than 16 elements), switch to Insertion Sort. Insertion Sort is faster than Quick Sort for very small arrays due to lower overhead.

🔎 Invariants, Trace, and Java Context

Safety Invariant

The algorithm behaves like Quick Sort while recursion is shallow. If depth reaches 2 * floor(log2(n)), the remaining partition is sorted with Heap Sort so the total work stays bounded by O(n log n).

Trace: Bad Pivot Run

Quick Sort keeps choosing highly unbalanced pivots.
The depth budget shrinks on each recursive level.
At zero budget, Heap Sort finishes that partition safely.

Java Library Note

IntroSort is famous from C++ std::sort. Java's standard library does not expose IntroSort as its default: primitive arrays use tuned Dual-Pivot Quicksort variants, while object arrays and lists use stable TimSort.

💻 Implementation

Python

python

INSERTION_THRESHOLD = 16

def introsort(values):
    """In-place introsort with half-open ranges [lo, hi)."""
    n = len(values)
    if n < 2:
        return values
    depth_limit = 2 * (n.bit_length() - 1)  # 2 * floor(log2(n))
    _introsort(values, 0, n, depth_limit)
    return values

def _introsort(values, lo, hi, depth_limit):
    while hi - lo > INSERTION_THRESHOLD:
        if depth_limit == 0:
            heap_sort_range(values, lo, hi)
            return
        depth_limit -= 1
        pivot = partition(values, lo, hi)

        # Recurse into the smaller side; iterate over the larger side.
        # This bounds the explicit call stack independently of pivot quality.
        if pivot - lo < hi - (pivot + 1):
            _introsort(values, lo, pivot, depth_limit)
            lo = pivot + 1
        else:
            _introsort(values, pivot + 1, hi, depth_limit)
            hi = pivot
    insertion_sort_range(values, lo, hi)

def partition(values, lo, hi):
    """Median-of-three Lomuto partition; returns final pivot index."""
    mid = lo + (hi - lo) // 2
    last = hi - 1
    if values[mid] < values[lo]:
        values[mid], values[lo] = values[lo], values[mid]
    if values[last] < values[lo]:
        values[last], values[lo] = values[lo], values[last]
    if values[last] < values[mid]:
        values[last], values[mid] = values[mid], values[last]
    values[mid], values[last] = values[last], values[mid]
    pivot_value = values[last]

    store = lo
    for i in range(lo, last):
        if values[i] < pivot_value:
            values[store], values[i] = values[i], values[store]
            store += 1
    values[store], values[last] = values[last], values[store]
    return store

def insertion_sort_range(values, lo, hi):
    for i in range(lo + 1, hi):
        item = values[i]
        j = i
        while j > lo and values[j - 1] > item:
            values[j] = values[j - 1]
            j -= 1
        values[j] = item

def heap_sort_range(values, lo, hi):
    size = hi - lo

    def sift_down(root, heap_size):
        item = values[lo + root]
        while 2 * root + 1 < heap_size:
            child = 2 * root + 1
            if child + 1 < heap_size and values[lo + child] < values[lo + child + 1]:
                child += 1
            if item >= values[lo + child]:
                break
            values[lo + root] = values[lo + child]
            root = child
        values[lo + root] = item

    for root in range(size // 2 - 1, -1, -1):
        sift_down(root, size)
    for end in range(size - 1, 0, -1):
        values[lo], values[lo + end] = values[lo + end], values[lo]
        sift_down(0, end)

data = [10, 7, 8, 9, 1, 5, 5, -3]
assert introsort(data) == sorted(data)
print(data)

Java

java

import java.util.Arrays;

public class IntroSort {
    
    // Threshold for switching to Insertion Sort
    private static final int INSERTION_THRESHOLD = 16;

    public static void sort(int[] arr) {
        if (arr.length < 2) return;
        int depthLimit = (int)(2 * Math.floor(Math.log(arr.length) / Math.log(2)));
        sort(arr, 0, arr.length - 1, depthLimit);
    }

    private static void sort(int[] arr, int begin, int end, int depthLimit) {
        int size = end - begin + 1;
        
        // Case 1: Small array -> Insertion Sort
        if (size < INSERTION_THRESHOLD) {
            insertionSort(arr, begin, end);
            return;
        }

        // Case 2: Recursion too deep -> Heap Sort
        if (depthLimit == 0) {
            heapSort(arr, begin, end);
            return;
        }

        // Case 3: Standard Quick Sort Partition
        int pivot = partition(arr, begin, end);
        sort(arr, begin, pivot - 1, depthLimit - 1);
        sort(arr, pivot + 1, end, depthLimit - 1);
    }

    // Standard Partition
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    // Standard Insertion Sort
    private static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    // Standard Heap Sort (on subarray)
    private static void heapSort(int[] arr, int begin, int end) {
        int n = end - begin + 1;
        // Build heap
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i, begin);
        // Extract
        for (int i = n - 1; i > 0; i--) {
            swap(arr, begin, begin + i);
            heapify(arr, i, 0, begin);
        }
    }

    private static void heapify(int[] arr, int n, int i, int offset) {
        int largest = i;
        int l = 2 * i + 1;
        int 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) {
            swap(arr, offset + i, offset + largest);
            heapify(arr, n, largest, offset);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = { 10, 7, 8, 9, 1, 5 };
        sort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Why the depth guard proves O(n log n)

initial budget

2⌊log₂ n⌋

A policy choice near twice the balanced-tree depth.

Exercises

Why is a depth limit of log2 n (without the factor 2) sometimes too aggressive?
On already-sorted data with a median-of-three pivot, does introsort still switch to heapsort often? Why?
Stability: which component breaks equal-key order, and when?

Primary sources

Musser, "Introspective Sorting and Selection Algorithms" (1997).
C++ std::sort complexity requirements and common libstdc++/libc++ introsort-based implementations.
Cormen et al., CLRS: quicksort and heapsort chapters as components.

each partition

budget − 1

Charged even when the split is badly unbalanced.

Exercises

Why is a depth limit of log2 n (without the factor 2) sometimes too aggressive?
On already-sorted data with a median-of-three pivot, does introsort still switch to heapsort often? Why?
Stability: which component breaks equal-key order, and when?

Primary sources

Musser, "Introspective Sorting and Selection Algorithms" (1997).
C++ std::sort complexity requirements and common libstdc++/libc++ introsort-based implementations.
Cormen et al., CLRS: quicksort and heapsort chapters as components.

at zero

Heap Sort the range

Deterministic O(m log m) for the remaining m items.

Exercises

Why is a depth limit of log2 n (without the factor 2) sometimes too aggressive?
On already-sorted data with a median-of-three pivot, does introsort still switch to heapsort often? Why?
Stability: which component breaks equal-key order, and when?

Primary sources

Musser, "Introspective Sorting and Selection Algorithms" (1997).
C++ std::sort complexity requirements and common libstdc++/libc++ introsort-based implementations.
Cormen et al., CLRS: quicksort and heapsort chapters as components.

Before fallback, any element participates in at most O(log n) partition levels because the budget caps path length. The fallback sorts disjoint remaining ranges in O(m log m), whose total is O(n log n). Small-range insertion sort has a fixed cutoff, so it contributes O(n) work. Together these establish the worst-case bound without sacrificing Quick Sort's typical locality.

Three invariants, one hybrid

Partition invariant

After partition, the pivot is final; left keys are smaller and right keys are not smaller under the chosen contract.

Budget invariant

Every active range carries the remaining partition allowance for its root-to-range path; it never resets on children.

Range invariant

Insertion and heap fallbacks operate only inside their range and cannot disturb pivots already fixed outside it.

Pivot attacks, duplicates, and fallback behavior

IntroSort adversarial inputs and mitigations
Input / threat	Quick-sort symptom	IntroSort response	Further tuning
Sorted + last pivot	Splits 0 and n−1 repeatedly	Depth reaches zero; heap fallback caps cost	Median-of-three reduces common ordered cases
Median-of-three killer	Crafted unbalanced samples	Same deterministic guardrail	Larger sampling/randomization changes constants and threat model
All/mostly equal	Two-way partitions make little progress	Fallback preserves O(n log n)	Three-way partition can make the equal region final in one pass
Tiny ranges	Call/partition overhead dominates	Insertion sort finishes cache-resident ranges	Benchmark the cutoff for type/comparator/hardware

A depth fallback is a safety mechanism, not a signal that pivot selection no longer matters. Better partitions reduce comparisons, fallback frequency, branch misses, and heap-sort locality costs on ordinary workloads.

Implementation and production checklist

• Guard n < 2 before computing logarithms; use integer bit length when possible.
• Recurse on the smaller partition and iterate on the larger to bound stack use.
• Heap-sort the current subrange with correct index offsets, not the entire array.
• Apply insertion sort only to small ranges or defer one final insertion pass.
• Document instability, comparator/null policy, mutation, and exception behavior.

• Test empty, singleton, sorted, reverse, organ-pipe, sawtooth, and duplicate-heavy arrays.
• Force depth exhaustion in a test and compare the fallback subrange with a trusted sort.
• Verify sortedness and permutation preservation; add tagged equals to expose instability.
• Test comparator transitivity violations separately; no comparison sort can repair an invalid comparator.
• Prefer the runtime library unless custom worst-case latency or instrumentation is required.

⚡ Complexity Analysis

Time Complexity

✓
O(n log n) - Worst Case
Guaranteed by switching to Heap Sort.
✓
O(n log n) - Average Case
Typical Quick Sort performance.

Space Complexity

✓
O(log n)
Stack space for recursion.

Tip: Why not just Heap Sort?

Heap Sort is O(n log n) guaranteed, but its constant factors are higher than Quick Sort (more swaps, poor cache locality). IntroSort uses Quick Sort for speed and only falls back to Heap Sort when necessary. It's the best of both worlds!

✅ Pros & ❌ Cons

✅ Advantages

✓Quick Sort-like average performance with a deterministic worst-case guardrail
✓Guaranteed O(n log n) worst case (like Heap Sort)
✓Efficient for small arrays (uses Insertion Sort)
✓Used by prominent standard-library implementations, including C++ std::sort families

❌ Disadvantages

✗Unstable sort (due to Quick Sort and Heap Sort)
✗More complex to implement than single algorithms