Какой алгоритм реализован внутри функции std::sort в C++?

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

• Быструю сортировку (Quicksort) для большинства случаев.
• Пирамидальную сортировку (Heapsort) для гарантированного худшего времени выполнения O(n log n), если глубина рекурсии становится слишком большой.
• Сортировку вставками (Insertion sort) для небольших подмассивов, что повышает эффективность.

Introsort начинается с быстрой сортировки, но если глубина рекурсии превышает определённый порог (обычно связанный с логарифмом размера массива), переключается на пирамидальную сортировку, чтобы избежать деградации производительности.

Это обеспечивает хорошую производительность в среднем и гарантированное время в худшем случае.