Aký algoritmus triedenia sa používa vo funkcii sort?

V štandardnej knižnici jazyka C++ je funkcia std::sort zvyčajne implementovaná pomocou algoritmu Introsort (Introspektívne zoradenie). Ide o hybridný algoritmus, ktorý kombinuje:

• Rýchle zoradenie (Quicksort) pre väčšinu prípadov
• Heapsort (Zoradenie na halde), ak sa hĺbka rekurzie stáva príliš veľká (aby sa predišlo najhoršiemu prípadu Quicksortu)
• Vkladacie zoradenie (Insertion Sort) pre malé podpolia

Introsort zabezpečuje priemerný dobrý výkon rýchleho zoradenia s garanciou najhoršieho prípadu O(n log n), vďaka prepnutiu na Heapsort.

Príklad použitia 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;
}

Preto je std::sort vysoko výkonný algoritmus založený na Introsort.