Jaki algorytm sortowania jest używany w funkcji sort?

W standardowej bibliotece C++ funkcja std::sort jest zwykle implementowana z użyciem algorytmu Introsort (Sortowanie introspekcyjne). Jest to hybrydowy algorytm, który łączy:

• Sortowanie szybkie (Quicksort) dla większości przypadków
• Sortowanie kopcowe (Heapsort) w przypadku, gdy głębokość rekurencji staje się zbyt duża (aby uniknąć najgorszego przypadku sortowania szybkiego)
• Sortowanie przez wstawianie (Insertion Sort) dla małych podtablic

Introsort zapewnia średnio dobrą wydajność sortowania szybkiego z gwarancją najgorszego przypadku O(n log n) dzięki przełączeniu na sortowanie kopcowe.

Przykład użycia 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;
}

Dlatego std::sort jest wysokowydajnym algorytmem opartym na Introsort.