Ce algoritm de sortare este utilizat în funcția sort?

În biblioteca standard C++, funcția std::sort este de obicei implementată folosind algoritmul Introsort (Sortare introspectivă). Este un algoritm hibrid care combină:

• Quicksort pentru majoritatea cazurilor
• Heapsort în cazul în care adâncimea recursiei devine prea mare (pentru a evita cel mai rău caz al Quicksort)
• Insertion Sort pentru subvectori mici

Introsort asigură, în medie, o performanță bună a Quicksort-ului cu garanția celui mai rău caz O(n log n), datorită trecerii la Heapsort.

Exemplu de utilizare a 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;
}

Prin urmare, std::sort este un algoritm de înaltă performanță bazat pe Introsort.