What sorting algorithm is used in the sort function?

In the standard C++ library, the std::sort function is usually implemented using the Introsort (Introspective Sort) algorithm. This hybrid algorithm combines:

• Quicksort for most cases
• Heapsort when the recursion depth becomes too large (to avoid the worst-case scenario of quicksort)
• Insertion Sort for small subarrays

Introsort provides good average performance of quicksort with a worst-case guarantee of O(n log n) by switching to heapsort.

Example of using 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;
}

Thus, std::sort is a high-performance algorithm based on Introsort.