Как устроена функция sort в C++ STL?

std::sort из заголовка <algorithm> — это гибридный алгоритм сортировки, который в большинстве реализаций (например, в libstdc++ и libc++) представляет собой Introsort.

Как работает Introsort:

1. Начинается как быстрая сортировка (Quicksort) с медианой из трёх для выбора опорного элемента.
2. Отслеживает глубину рекурсии. Если она превышает 2 * log₂(n), алгоритм переключается на пирамидальную сортировку (Heapsort). Это гарантирует сложность O(n log n) в худшем случае и предотвращает деградацию до O(n²) на специально подобранных данных.
3. Для маленьких подмассивов (обычно размером менее 16-32 элементов) часто применяется сортировка вставками (Insertion Sort) из-за её эффективности на небольших наборах.

Синтаксис и использование:

#include <algorithm>
#include <vector>
#include <functional>

std::vector<int> data = {5, 1, 4, 2, 8};

// 1. Сортировка по возрастанию (использует operator<)
std::sort(data.begin(), data.end());

// 2. Сортировка по убыванию с использованием функционального объекта
std::sort(data.begin(), data.end(), std::greater<int>());

// 3. Сортировка с пользовательским компаратором (лямбда)
std::sort(data.begin(), data.end(), [](int a, int b) {
    return (a % 3) < (b % 3); // Сортировка по остатку от деления на 3
});

Ключевые особенности std::sort:

• Требует итераторов произвольного доступа: Работает с std::vector, std::deque, std::array и обычными массивами. Не работает с std::list (для него есть метод list::sort()).
• Нестабильная: Не сохраняет относительный порядок равных элементов. Для стабильной сортировки используйте std::stable_sort.
• Компаратор: Должен обеспечивать строгое слабое упорядочение. Например, для сортировки по убыванию корректно использовать std::greater<>(), а не [](int a, int b) { return a > b; } (хотя лямбда также допустима).