Jaký třídicí algoritmus se používá ve funkci sort?

V knihovně standardu C++ je funkce std::sort obvykle implementována pomocí algoritmu Introsort (Introspektivní třídění). Je to hybridní algoritmus, který kombinuje:

• Rychlé třídění (Quicksort) pro většinu případů
• Heapsort, pokud se hloubka rekurze stává příliš velkou (aby se předešlo nejhoršímu případu Quicksortu)
• Vkládací třídění (Insertion Sort) pro malé podpole

Introsort zajišťuje průměrně dobrou výkonnost rychlého třídění s garancí nejhoršího případu O(n log n), díky přepínání na Heapsort.

Příklad použití 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;
}

Proto je std::sort vysoce výkonný algoritmus založený na Introsortu.