Introselect

Introselect is a hybrid selection algorithm. It starts with Quickselect for speed and switches to a worst-case linear method when recursion becomes too deep.

This design mirrors Introsort. The goal is to keep the fast average behavior of Quickselect while guaranteeing linear worst-case time.

Problem

Given an array $A$ and integer $k$ , find the k-th smallest element with both practical efficiency and worst-case guarantees.

Algorithm

Run Quickselect with a recursion depth limit. If the depth exceeds a threshold, switch to Deterministic Select.

introselect(A, k):
    max_depth = 2 * floor(log2(length(A)))

    return introselect_recursive(A, k, max_depth)

introselect_recursive(A, k, depth):
    if length(A) <= small_threshold:
        sort A
        return A[k]

    if depth == 0:
        return deterministic_select(A, k)

    pivot = choose_pivot(A)

    partition A into L, E, R

    if k < length(L):
        return introselect_recursive(L, k, depth - 1)
    else if k < length(L) + length(E):
        return pivot
    else:
        return introselect_recursive(R, k - length(L) - length(E), depth - 1)

Key Idea

Quickselect is fast in practice but can degrade to quadratic time. Depth monitoring detects this degeneration early. When recursion becomes too deep, the algorithm switches to a guaranteed linear method.

Correctness

Each step preserves the rank invariant through partitioning. The fallback method is correct by construction. Therefore the hybrid remains correct.

Complexity

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

Worst-case linear time comes from switching to Deterministic Select.

Space:

O(1)

for in-place version.

When to Use

Use Introselect when:

you want production-grade selection
input may be adversarial
both speed and guarantees matter

It is a practical default in high-performance libraries.

Implementation

import math
import random

def introselect(a, k):
    def partition(left, right, pivot_index):
        pivot = a[pivot_index]
        a[pivot_index], a[right] = a[right], a[pivot_index]
        store = left
        for i in range(left, right):
            if a[i] < pivot:
                a[store], a[i] = a[i], a[store]
                store += 1
        a[right], a[store] = a[store], a[right]
        return store

    def select(left, right, k, depth):
        if left == right:
            return a[left]

        if depth == 0:
            return deterministic_select(a[left:right+1], k - left)

        pivot_index = random.randint(left, right)
        pivot_index = partition(left, right, pivot_index)

        if k == pivot_index:
            return a[k]
        elif k < pivot_index:
            return select(left, pivot_index - 1, k, depth - 1)
        else:
            return select(pivot_index + 1, right, k, depth - 1)

    max_depth = 2 * int(math.log2(len(a))) if len(a) > 0 else 0
    return select(0, len(a) - 1, k, max_depth)

import (
	"math"
	"math/rand"
)

func Introselect(a []int, k int) int {
	maxDepth := 0
	if len(a) > 0 {
		maxDepth = 2 * int(math.Log2(float64(len(a))))
	}

	var selectFn func(int, int, int, int) int

	selectFn = func(left, right, k, depth int) int {
		if left == right {
			return a[left]
		}

		if depth == 0 {
			return DeterministicSelect(a[left:right+1], k-left)
		}

		pivotIndex := left + rand.Intn(right-left+1)
		pivotIndex = partition(a, left, right, pivotIndex)

		if k == pivotIndex {
			return a[k]
		} else if k < pivotIndex {
			return selectFn(left, pivotIndex-1, k, depth-1)
		} else {
			return selectFn(pivotIndex+1, right, k, depth-1)
		}
	}

	return selectFn(0, len(a)-1, k, maxDepth)
}