Introsort

function introsort(arr, depth = 0) {
    const maxDepth = 2 * Math.floor(Math.log2(arr.length));

    if (arr.length <= 16) {
        // Use insertion sort for small arrays
        insertionSortSmall(arr);
    } else if (depth >= maxDepth) {
        // Switch to heap sort if recursion too deep
        heapSortIntrospective(arr);
    } else {
        // Use quicksort with depth tracking
        const pivotIndex = partitionIntrospective(arr, depth);
        introsort(arr.slice(0, pivotIndex), depth + 1);
        introsort(arr.slice(pivotIndex + 1), depth + 1);
    }

    return arr;
}

function partitionIntrospective(arr, depth) {
    // Median-of-three pivot selection
    const mid = Math.floor(arr.length / 2);
    const candidates = [
        { value: arr[0], index: 0 },
        { value: arr[mid], index: mid },
        { value: arr[arr.length - 1], index: arr.length - 1 }
    ];

    // Sort candidates
    candidates.sort((a, b) => a.value - b.value);

    // Place median pivot at end
    [arr[candidates[1].index], arr[arr.length - 1]] =
    [arr[arr.length - 1], arr[candidates[1].index]];

    // Standard partition
    const pivot = arr[arr.length - 1];
    let i = -1;

    for (let j = 0; j < arr.length - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }

    [arr[i + 1], arr[arr.length - 1]] = [arr[arr.length - 1], arr[i + 1]];
    return i + 1;
}

function insertionSortSmall(arr) {
    for (let i = 1; i < arr.length; i++) {
        const key = arr[i];
        let j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

function heapSortIntrospective(arr) {
    // Build max heap
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
        heapifyIntrospective(arr, arr.length, i);
    }

    // Extract elements
    for (let i = arr.length - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        heapifyIntrospective(arr, i, 0);
    }
}

function heapifyIntrospective(arr, n, i) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapifyIntrospective(arr, n, largest);
    }
}

How Introsort Works

Introsort combines the best aspects of quicksort, heapsort, and insertion sort. It starts with quicksort but monitors the recursion depth, switching to heapsort if quicksort appears to be degrading to O(n²) performance.

Algorithm Strategy:

1. Start with Quicksort: Use fast quicksort for most cases
2. Monitor Depth: Track recursion depth to detect worst-case behavior
3. Depth Limit: Calculate limit based on 2×log₂(n)
4. Switch to Heapsort: When depth limit exceeded, use guaranteed O(n log n)
5. Small Arrays: Use insertion sort for arrays ≤ 16 elements

Key Innovations:

• Introspective: Monitors its own performance characteristics
• Hybrid approach: Uses best algorithm for current situation
• Worst-case guarantee: Always O(n log n) performance
• Adaptive switching: Changes strategy based on runtime behavior

Why Introsort is Important:

• C++ Standard Library: Used in std::sort() since C++11
• Real-world performance: Combines speed with reliability
• Industry standard: Proves hybrid algorithms work in practice
• Research influence: Changed how we think about sorting algorithm design

Performance Characteristics:

• Best Case: O(n log n) with good pivot selection
• Average Case: O(n log n) same as quicksort
• Worst Case: O(n log n) guaranteed (no O(n²) degradation)
• Adaptive: Maintains quicksort's speed while preventing worst case

Technical Details:

• Depth limit: 2×⌊log₂(n)⌋ prevents excessive recursion
• Median-of-three: Better pivot selection than simple quicksort
• Small array threshold: 16 elements for insertion sort
• Memory efficient: In-place sorting with O(log n) stack space

Real-World Impact:

• C++ std::sort(): Default sorting algorithm in C++ standard library
• Performance critical: Used in high-performance applications
• Library implementation: Shows how hybrid algorithms work in practice
• Algorithm design: Influenced modern sorting algorithm development

Design Philosophy:

Educational Value:

• Hybrid algorithm design: Shows how to combine multiple approaches
• Performance monitoring: Demonstrates self-aware algorithm behavior
• Practical engineering: Real-world algorithm design considerations
• Industry relevance: Used in major programming language libraries