Какой алгоритм используется в std::sort?

std::sort использует Introsort (Introspective Sort)

sdt::sort — это одна из самых важных функций стандартной библиотеки C++. Её реализация использует гибридный алгоритм Introsort, который комбинирует несколько подходов для оптимальной производительности.

Основные компоненты Introsort

Introsort состоит из трёх алгоритмов:

1. QuickSort — основной алгоритм на начальных этапах, очень быстрый в среднем случае
2. HeapSort — резервный алгоритм, если QuickSort деградирует (худший случай O(n²))
3. InsertionSort — для сортировки малых подмассивов (обычно < 16 элементов)

Как это работает

void introsort(int* arr, int size) {
    int depth_limit = 2 * log(size);  // Лимит глубины рекурсии
    introsort_helper(arr, 0, size - 1, depth_limit);
}

void introsort_helper(int* arr, int lo, int hi, int depth) {
    while (hi - lo > 16) {  // Порог переключения на InsertionSort
        if (depth == 0) {
            // QuickSort деградировал - переходим на HeapSort
            heapsort(arr, lo, hi + 1);
            return;
        }
        
        // Выполняем QuickSort шаг с выбором опорного элемента
        int p = partition(arr, lo, hi);
        introsort_helper(arr, p + 1, hi, depth - 1);
        hi = p - 1;
        depth--;
    }
    
    // Финальная сортировка InsertionSort для малых массивов
    insertion_sort(arr, lo, hi + 1);
}

Почему Introsort лучше обычного QuickSort?

Гарантированная сложность:

• QuickSort имеет худший случай O(n²) на отсортированных или почти отсортированных данных
• Introsort гарантирует O(n log n) благодаря переключению на HeapSort
• Это обеспечивает предсказуемую производительность

Кэш-эффективность:

• QuickSort хорошо работает с кэшем процессора благодаря локальности ссылок
• HeapSort используется редко, только в патологических случаях
• InsertionSort оптимален для малых данных (низкие накладные расходы)

Адаптивность:

• Выбор опорного элемента часто использует медиану-из-трёх
• Если данные уже частично отсортированы, QuickSort быстро завершится
• Глубина рекурсии отслеживается для раннего обнаружения деградации

Реализации в разных компиляторах

• GCC libstdc++ — Introsort с 3-way partition для обработки дублей
• MSVC STL — версия Introsort с оптимизацией для Windows
• Clang libc++ — похожий подход, но с некоторыми отличиями в деталях

Временная сложность

Альтернативы

std::stable_sort — сохраняет относительный порядок равных элементов, использует MergeSort, O(n log n) всегда.

std::partial_sort — сортирует только первые N элементов, полезна для top-N операций.

boost::sort::pdqsort — более современный алгоритм Pattern-Defeating QuickSort, часто быстрее Introsort на реальных данных.

Выбор Introsort — это оптимальный компромисс между скоростью (QuickSort), надёжностью (HeapSort) и простотой реализации.