Introsort

Introsort, short for introspective sort, is a hybrid sorting algorithm. It starts with quicksort because quicksort is fast in practice. It monitors recursion depth, and when the recursion becomes too deep, it switches to heapsort to avoid quadratic worst case behavior.

This gives the practical speed of quicksort with the worst case guarantee of heapsort.

Problem

Given an array $A$ of length $n$ , reorder it such that:

A[0] \le A[1] \le \dots \le A[n-1]

Idea

Quicksort is usually fast, but it can degrade to:

O(n^2)

when partitioning is repeatedly unbalanced. Introsort limits this risk by setting a maximum recursion depth:

2\lfloor \log_2 n \rfloor

If the recursion exceeds this limit, the algorithm sorts the current subarray using heapsort.

Algorithm

introsort(A):
    depth_limit = 2 * floor(log2(length(A)))
    introsort_loop(A, 0, length(A) - 1, depth_limit)

introsort_loop(A, lo, hi, depth_limit):
    if lo >= hi:
        return

    if depth_limit == 0:
        heapsort_range(A, lo, hi)
        return

    p = partition(A, lo, hi)

    introsort_loop(A, lo, p - 1, depth_limit - 1)
    introsort_loop(A, p + 1, hi, depth_limit - 1)

Example

Let:

A = [9, 1, 8, 2, 7, 3]

Introsort begins like quicksort:

choose a pivot
partition the array
recurse on both sides

If partitioning remains balanced, it behaves like quicksort. If partitioning becomes repeatedly unbalanced, the depth limit is eventually reached and heapsort handles the remaining range.

Correctness

Before the depth limit is reached, introsort uses quicksort partitioning. Each partition places the pivot into its final sorted position and divides the problem into smaller independent subarrays.

When the depth limit is reached, heapsort sorts the remaining subarray correctly. Since every recursive branch either completes through quicksort or falls back to a correct sorting algorithm, the final array is sorted.

Complexity

case	time
best	$O(n \log n)$
average	$O(n \log n)$
worst	$O(n \log n)$

Space:

source	space
recursion stack	$O(\log n)$ average
heapsort fallback	$O(1)$ extra

Properties

property	value
stable	no
in-place	yes
hybrid	quicksort plus heapsort
worst case guarantee	$O(n \log n)$
practical performance	high

Notes

Many standard libraries use introsort or introsort-like algorithms for general purpose unstable sorting. A common practical variant also switches to insertion sort for very small subarrays.

This combination gives good constants, bounded worst case behavior, and low memory usage.

Implementation

import math

def introsort(a):
    if len(a) <= 1:
        return a

    depth_limit = 2 * math.floor(math.log2(len(a)))

    def sort(lo, hi, depth):
        if lo >= hi:
            return

        if depth == 0:
            heap_sort_range(lo, hi)
            return

        p = partition(lo, hi)
        sort(lo, p - 1, depth - 1)
        sort(p + 1, hi, depth - 1)

    def partition(lo, hi):
        pivot = a[hi]
        i = lo

        for j in range(lo, hi):
            if a[j] <= pivot:
                a[i], a[j] = a[j], a[i]
                i += 1

        a[i], a[hi] = a[hi], a[i]
        return i

    def heap_sort_range(lo, hi):
        b = a[lo:hi + 1]

        def sift_down(start, end):
            root = start
            while 2 * root + 1 <= end:
                child = 2 * root + 1
                swap = root

                if b[swap] < b[child]:
                    swap = child
                if child + 1 <= end and b[swap] < b[child + 1]:
                    swap = child + 1
                if swap == root:
                    return

                b[root], b[swap] = b[swap], b[root]
                root = swap

        n = len(b)

        for start in range((n - 2) // 2, -1, -1):
            sift_down(start, n - 1)

        for end in range(n - 1, 0, -1):
            b[end], b[0] = b[0], b[end]
            sift_down(0, end - 1)

        a[lo:hi + 1] = b

    sort(0, len(a) - 1, depth_limit)
    return a

import "math/bits"

func IntroSort(a []int) {
	n := len(a)
	if n <= 1 {
		return
	}

	depthLimit := 2 * (bits.Len(uint(n)) - 1)

	var sort func(int, int, int)
	sort = func(lo, hi, depth int) {
		if lo >= hi {
			return
		}

		if depth == 0 {
			heapSortRange(a, lo, hi)
			return
		}

		p := introPartition(a, lo, hi)
		sort(lo, p-1, depth-1)
		sort(p+1, hi, depth-1)
	}

	sort(0, n-1, depthLimit)
}

func introPartition(a []int, lo, hi int) int {
	pivot := a[hi]
	i := lo

	for j := lo; j < hi; j++ {
		if a[j] <= pivot {
			a[i], a[j] = a[j], a[i]
			i++
		}
	}

	a[i], a[hi] = a[hi], a[i]
	return i
}

func heapSortRange(a []int, lo, hi int) {
	n := hi - lo + 1

	siftDown := func(start, end int) {
		root := start

		for 2*root+1 <= end {
			child := 2*root + 1
			swap := root

			if a[lo+swap] < a[lo+child] {
				swap = child
			}
			if child+1 <= end && a[lo+swap] < a[lo+child+1] {
				swap = child + 1
			}
			if swap == root {
				return
			}

			a[lo+root], a[lo+swap] = a[lo+swap], a[lo+root]
			root = swap
		}
	}

	for start := (n - 2) / 2; start >= 0; start-- {
		siftDown(start, n-1)
		if start == 0 {
			break
		}
	}

	for end := n - 1; end > 0; end-- {
		a[lo+end], a[lo] = a[lo], a[lo+end]
		siftDown(0, end-1)
	}
}