IntroSort (Introspective Sort / Интроспективная сортировка)

Краткое описание

Гибридный алгоритм сортировки, комбинирующий Quick Sort, Heap Sort и Insertion Sort. Начинает с Quick Sort, но следит за глубиной рекурсии — если она превышает 2×log(n), переключается на Heap Sort, избегая худшего случая O(n²). Для малых подмассивов использует Insertion Sort. Используется в C++ STL std::sort.

Когда использовать

• Production код на C++ — это алгоритм за std::sort в стандартной библиотеке
• Нужна гарантированная O(n log n) БЕЗ дополнительной памяти — сочетает скорость Quick Sort с гарантиями Heap Sort
• Универсальный выбор — работает эффективно на любых данных, не имеет худшего случая O(n²)
• Большие массивы в памяти — очень быстрый на практике благодаря Quick Sort как основному алгоритму
• Критична производительность — оптимален для большинства реальных сценариев

Когда не стоит использовать:

• Нужна стабильность — IntroSort не стабильный, как и Quick Sort
• Маленькие массивы — для массивов < 16 элементов обычный Insertion Sort может быть проще
• Почти отсортированные данные — TimSort будет эффективнее благодаря адаптивности
• Простота реализации важна — один из самых сложных алгоритмов для имплементации

---

С объяснением логики работы

/**
 * IntroSort — гибридная сортировка
 * 
 * Стратегия:
 * 1. Начинаем с Quick Sort (быстрый на практике)
 * 2. Следим за глубиной рекурсии
 * 3. Если глубина > 2*log(n) → переключаемся на Heap Sort (избегаем O(n²))
 * 4. Для малых подмассивов (< 16 элементов) → Insertion Sort
 */
 
// Порог для переключения на Insertion Sort
const INSERTION_SORT_THRESHOLD = 16;
 
/**
 * Insertion Sort для малых подмассивов
 */
function insertionSort(arr, left, right) {
    for (let i = left + 1; i <= right; i++) {
        const key = arr[i];
        let j = i - 1;
 
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
 
/**
 * Heapify для Heap Sort
 */
function heapify(arr, n, i, offset) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
 
    if (left < n && arr[offset + left] > arr[offset + largest]) {
        largest = left;
    }
 
    if (right < n && arr[offset + right] > arr[offset + largest]) {
        largest = right;
    }
 
    if (largest !== i) {
        [arr[offset + i], arr[offset + largest]] = 
            [arr[offset + largest], arr[offset + i]];
        heapify(arr, n, largest, offset);
    }
}
 
/**
 * Heap Sort для подмассива
 */
function heapSort(arr, left, right) {
    const n = right - left + 1;
 
    // Строим max-heap
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i, left);
    }
 
    // Извлекаем элементы из кучи
    for (let i = n - 1; i > 0; i--) {
        [arr[left], arr[left + i]] = [arr[left + i], arr[left]];
        heapify(arr, i, 0, left);
    }
}
 
/**
 * Partition для Quick Sort (Lomuto scheme)
 */
function partition(arr, left, right) {
    // Медиана из трёх для выбора pivot (оптимизация)
    const mid = Math.floor((left + right) / 2);
 
    // Упорядочиваем arr[left], arr[mid], arr[right]
    if (arr[mid] < arr[left]) {
        [arr[left], arr[mid]] = [arr[mid], arr[left]];
    }
    if (arr[right] < arr[left]) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
    }
    if (arr[right] < arr[mid]) {
        [arr[mid], arr[right]] = [arr[right], arr[mid]];
    }
 
    // Используем медиану как pivot
    const pivot = arr[mid];
    [arr[mid], arr[right - 1]] = [arr[right - 1], arr[mid]];
 
    let i = left;
    let j = right - 1;
 
    while (true) {
        while (arr[++i] < pivot) {}
        while (arr[--j] > pivot) {}
 
        if (i >= j) break;
 
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
 
    [arr[i], arr[right - 1]] = [arr[right - 1], arr[i]];
    return i;
}
 
/**
 * Внутренняя рекурсивная функция IntroSort
 */
function introSortHelper(arr, left, right, maxDepth) {
    const size = right - left + 1;
 
    // ОПТИМИЗАЦИЯ 1: Для малых массивов используем Insertion Sort
    // Insertion Sort эффективнее на малых данных из-за меньших накладных расходов
    if (size <= INSERTION_SORT_THRESHOLD) {
        insertionSort(arr, left, right);
        return;
    }
 
    // ОПТИМИЗАЦИЯ 2: Если глубина рекурсии слишком большая
    // значит Quick Sort деградирует до O(n²)
    // Переключаемся на Heap Sort с гарантированной O(n log n)
    if (maxDepth === 0) {
        heapSort(arr, left, right);
        return;
    }
 
    // Основной случай: используем Quick Sort
    const pivotIndex = partition(arr, left, right);
 
    // Рекурсивно сортируем части, уменьшая maxDepth
    introSortHelper(arr, left, pivotIndex - 1, maxDepth - 1);
    introSortHelper(arr, pivotIndex + 1, right, maxDepth - 1);
}
 
/**
 * Основная функция IntroSort
 */
function introSort(arr) {
    if (arr.length <= 1) return arr;
 
    // Вычисляем максимальную глубину рекурсии: 2 * log₂(n)
    // Это эмпирически оптимальное значение
    const maxDepth = Math.floor(2 * Math.log2(arr.length));
 
    introSortHelper(arr, 0, arr.length - 1, maxDepth);
 
    return arr;
}
 
// Пример использования
const numbers = [64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 22, 3, 99, 1];
console.log("Исходный массив:", numbers);
introSort(numbers);
console.log("Отсортированный массив:", numbers);
 
/**
 * ПОЧЕМУ INTROSORT ЭФФЕКТИВЕН:
 * 
 * 1. БЫСТРЫЙ В СРЕДНЕМ
 *    Quick Sort — один из самых быстрых на практике
 * 
 * 2. ГАРАНТИРОВАННАЯ ПРОИЗВОДИТЕЛЬНОСТЬ
 *    Heap Sort предотвращает деградацию до O(n²)
 * 
 * 3. ОПТИМАЛЕН НА МАЛЫХ ДАННЫХ
 *    Insertion Sort для подмассивов < 16 элементов
 * 
 * 4. МЕДИАНА ИЗ ТРЁХ
 *    Лучший выбор pivot, чем случайный или первый элемент
 */

---

С анализом сложностей

/**
 * IntroSort с анализом сложности
 * 
 * ВРЕМЕННАЯ СЛОЖНОСТЬ:
 * - Лучший случай:   O(n log n) — Quick Sort с хорошими разбиениями
 * - Средний случай:  O(n log n) — типичная работа Quick Sort
 * - Худший случай:   O(n log n) — ГАРАНТИРОВАННО! Heap Sort предотвращает O(n²)
 * 
 * ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ:
 * - O(log n) — стек рекурсии для Quick Sort
 * - O(1) дополнительной памяти (in-place)
 * 
 * ОСОБЕННОСТИ:
 * - НЕ стабильный (как Quick Sort)
 * - Гибридный: комбинирует 3 алгоритма
 * - Production-ready: используется в C++ STL
 */
 
const INSERTION_SORT_THRESHOLD = 16;
 
function insertionSort(arr, left, right) {
    // ВРЕМЕННАЯ СЛОЖНОСТЬ: O((right-left)²)
    // Для малых массивов (≤16): константное время
    // O(16²) = O(256) = O(1)
 
    for (let i = left + 1; i <= right; i++) {
        const key = arr[i];
        let j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
 
function heapify(arr, n, i, offset) {
    // O(log n) — высота дерева
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
 
    if (left < n && arr[offset + left] > arr[offset + largest]) {
        largest = left;
    }
    if (right < n && arr[offset + right] > arr[offset + largest]) {
        largest = right;
    }
 
    if (largest !== i) {
        [arr[offset + i], arr[offset + largest]] = 
            [arr[offset + largest], arr[offset + i]];
        heapify(arr, n, largest, offset);
    }
}
 
function heapSort(arr, left, right) {
    // ВРЕМЕННАЯ СЛОЖНОСТЬ: O(n log n) гарантированно
    // Используется как "страховка" от худшего случая Quick Sort
 
    const n = right - left + 1;
 
    // Build heap: O(n)
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i, left);
    }
 
    // Extract elements: O(n log n)
    for (let i = n - 1; i > 0; i--) {
        [arr[left], arr[left + i]] = [arr[left + i], arr[left]];
        heapify(arr, i, 0, left);
    }
}
 
function partition(arr, left, right) {
    // ВРЕМЕННАЯ СЛОЖНОСТЬ: O(right - left) = O(n)
    // 
    // ОПТИМИЗАЦИЯ: Медиана из трёх
    // Вместо случайного pivot или первого элемента,
    // выбираем медиану из arr[left], arr[mid], arr[right]
    // Это значительно снижает вероятность плохих разбиений
 
    const mid = Math.floor((left + right) / 2);
 
    // Сортируем три элемента: O(1)
    if (arr[mid] < arr[left]) {
        [arr[left], arr[mid]] = [arr[mid], arr[left]];
    }
    if (arr[right] < arr[left]) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
    }
    if (arr[right] < arr[mid]) {
        [arr[mid], arr[right]] = [arr[right], arr[mid]];
    }
 
    const pivot = arr[mid];
    [arr[mid], arr[right - 1]] = [arr[right - 1], arr[mid]];
 
    let i = left;
    let j = right - 1;
 
    // Partition: O(n)
    while (true) {
        while (arr[++i] < pivot) {}
        while (arr[--j] > pivot) {}
        if (i >= j) break;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
 
    [arr[i], arr[right - 1]] = [arr[right - 1], arr[i]];
    return i;
}
 
function introSortHelper(arr, left, right, maxDepth) {
    const size = right - left + 1;
 
    // ВЕТВЛЕНИЕ 1: Малые массивы
    // ПОЧЕМУ 16? Эмпирически найденное оптимальное значение
    // - Insertion Sort быстрее на малых данных
    // - Меньше накладных расходов на рекурсию
    // - Лучшая cache locality
    if (size <= INSERTION_SORT_THRESHOLD) {
        insertionSort(arr, left, right);  // O(size²) но size ≤ 16
        return;
    }
 
    // ВЕТВЛЕНИЕ 2: Превышена глубина рекурсии
    // ПОЧЕМУ maxDepth = 2*log(n)?
    // - log(n) — ожидаемая глубина для хорошо сбалансированного Quick Sort
    // - 2*log(n) — запас на небольшие дисбалансы
    // - Если превышено → плохие разбиения → переключаемся на Heap Sort
    if (maxDepth === 0) {
        heapSort(arr, left, right);  // O(n log n) гарантированно
        return;
    }
 
    // ОСНОВНОЙ СЛУЧАЙ: Quick Sort
    // АНАЛИЗ:
    // - Partition: O(n)
    // - Две рекурсии: T(k) + T(n-k-1)
    // - При хороших разбиениях: T(n) = 2T(n/2) + O(n) = O(n log n)
    // - При плохих: защищены maxDepth и переключением на Heap Sort
    const pivotIndex = partition(arr, left, right);
 
    introSortHelper(arr, left, pivotIndex - 1, maxDepth - 1);
    introSortHelper(arr, pivotIndex + 1, right, maxDepth - 1);
}
 
function introSort(arr) {
    if (arr.length <= 1) return arr;
 
    // КЛЮЧЕВОЙ ПАРАМЕТР: maxDepth = 2 * log₂(n)
    // 
    // Примеры:
    // n = 100:     maxDepth = 2 * 6.64 ≈ 13
    // n = 1000:    maxDepth = 2 * 9.97 ≈ 20
    // n = 1000000: maxDepth = 2 * 19.93 ≈ 40
    // 
    // Это позволяет Quick Sort работать нормально,
    // но предотвращает деградацию до O(n²)
    const maxDepth = Math.floor(2 * Math.log2(arr.length));
 
    introSortHelper(arr, 0, arr.length - 1, maxDepth);
 
    return arr;
}
 
// ИТОГОВАЯ СЛОЖНОСТЬ:
// 
// Время:  O(n log n) в ЛЮБОМ случае
// Память: O(log n) для стека рекурсии
//
// СРАВНЕНИЕ С ДРУГИМИ АЛГОРИТМАМИ:
//
// IntroSort vs Quick Sort:
// ✓ IntroSort гарантирует O(n log n), Quick Sort может O(n²)
// ✓ IntroSort использует Insertion Sort для малых массивов
// ✓ IntroSort использует медиану из трёх для pivot
// = Оба in-place и нестабильные
//
// IntroSort vs Heap Sort:
// ✓ IntroSort быстрее на практике (большую часть времени Quick Sort)
// ✓ IntroSort лучшая cache locality
// = Оба гарантируют O(n log n)
// = Оба in-place и нестабильные
//
// IntroSort vs Merge Sort:
// ✓ IntroSort не требует O(n) памяти
// ✗ IntroSort не стабильный
// = Оба гарантируют O(n log n)
//
// IntroSort vs TimSort:
// ✓ IntroSort быстрее на случайных данных
// ✓ IntroSort использует меньше памяти
// ✗ IntroSort не адаптивный
// ✗ IntroSort не стабильный
//
// ПОЧЕМУ C++ STL ИСПОЛЬЗУЕТ INTROSORT:
// 1. Гарантированная O(n log n) — нет худшего случая
// 2. Очень быстрый на практике — Quick Sort как основа
// 3. In-place — O(log n) памяти
// 4. Оптимизирован для разных сценариев
// 5. Проверен временем в production
 
// Примеры производительности:
 
// Случайные данные: работает как Quick Sort — очень быстро
const random = Array.from({length: 1000}, () => Math.random());
 
// Отсортированные данные: не деградирует благодаря медиане из трёх
const sorted = Array.from({length: 1000}, (_, i) => i);
 
// Обратный порядок: не деградирует благодаря maxDepth и Heap Sort
const reversed = Array.from({length: 1000}, (_, i) => 1000 - i);
 
// Все одинаковые: медиана из трёх помогает
const same = Array.from({length: 1000}, () => 42);