В стандартной библиотеке C++ функция std::sort обычно реализована с использованием алгоритма Introsort (Introspective Sort). Это гибридный алгоритм, который сочетает в себе:

Быструю сортировку (Quicksort) для большинства случаев
Пирамидальную сортировку (Heapsort) в случае, если глубина рекурсии становится слишком большой (чтобы избежать худшего случая быстрой сортировки)
Сортировку вставками (Insertion Sort) для небольших подмассивов

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

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

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

int main() {
    std::vector<int> v = {5, 3, 2, 4, 1};
    std::sort(v.begin(), v.end());
    for (int n : v) {
        std::cout << n << ' ';
    }
    return 0;
}

Таким образом, std::sort — это высокопроизводительный алгоритм, основанный на Introsort.

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