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

Реализация std::sort в стандартной библиотеке C++ (например, в libstdc++ и libc++) использует гибридный алгоритм Introsort (интроспективная сортировка).

Introsort — это комбинация трех алгоритмов:

1. Quicksort — используется как основной алгоритм для больших массивов благодаря хорошей средней производительности.
2. Heapsort — включается, когда глубина рекурсии Quicksort превышает порог (обычно 2 * log(n)), чтобы гарантировать сложность O(n log n) в худшем случае и избежать деградации до O(n²).
3. Insertion sort — применяется для маленьких подмассивов (обычно размером меньше 16 элементов), так как он эффективен на почти отсортированных данных и имеет низкие накладные расходы.

Пример использования:

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> data = {42, 17, -5, 0, 23, 100, 8};
    // Используется Introsort
    std::sort(data.begin(), data.end());
    // data теперь: {-5, 0, 8, 17, 23, 42, 100}
    for (int val : data) {
        std::cout << val << ' ';
    }
    return 0;
}

Ключевые характеристики std::sort:

• Сложность: O(n log n) в среднем и худшем случае.
• Нестабильность: Не гарантирует сохранение относительного порядка равных элементов. Для стабильной сортировки используйте std::stable_sort.
• Требования: Элементы должны поддерживать операцию сравнения "меньше" (operator<) или должен быть предоставлен пользовательский компаратор.