Стандартом не оговаривается какой именно алгоритм должен быть под капотом std::sort. Однако можно подглядеть как реализован std::sort, например, в gcc.

Там работает QuickSort, который переключается на HeapSort если глубина рекурсии превышает 2 логарифма от количества элементов. Также для количества элементов меньше 16 включается сортировка вставками. Опорный элемент для QuickSort выбирается как медиана из первого, последнего и элемента посередине.

Сложность сей конструкции всё равно N * Log(N)

Introsort. Сначала quicksort, но если глубина рекурсии слишком большая, переключается на heap sort; таким образом, сложность равна O(n log n) и в среднем, и в худшем случае, но в среднем случае используется самый быстрый алгоритм с этой сложностью. Плюс для пущей скорости на маленьких отрезках делается ни то и ни другое, а insertion sort (но это не влияет на асимптотику).

Как отметили выше, стандарт не оговаривает конкретный алгоритм, но сложность обязательно должна быть O(n log n). Таким образом, простой quicksort недопустим (потому что у него в худшем случае n²), но разрешается не только introsort, но и, например, heap sort, merge sort или ещё что-нибудь более экзотическое. Однако на практике introsort быстрее всего и поэтому используется именно он.