http://www.cplusplus.com/reference/algorithm/sort/

https://en.wikipedia.org/wiki/Sort_(C%2B%2B)

Complexity and implementations[edit]

The C++ standard requires that a call to sort performs O(N log N) comparisons when applied to a range of N elements.^[4] In previous versions of C++, such as C++03, only average complexity was required to be O(N log N).^[5] This was to allow the use of algorithms like (median-of-3) quicksort, which are fast in the average case, indeed significantly faster than other algorithms like heap sort with optimal worst-case complexity, and where the worst-case quadratic complexity rarely occurs.^[6] The introduction of hybrid algorithms such as introsort allowed both fast average performance and optimal worst-case performance, and thus the complexity requirements were tightened in later standards.

Different implementations use different algorithms. The GNU Standard C++ library, for example, uses a 3-part hybrid sorting algorithm: introsort is performed first (introsort itself being a hybrid of quicksort and heap sort), to a maximum depth given by 2×log₂ n, where n is the number of elements, followed by an insertion sort on the result.^[7]