Кой алгоритъм за сортиране се използва във функцията sort?

В стандартната библиотека на C++ функцията std::sort обикновено се реализира с използване на алгоритъма Introsort (Интроспективно сортиране). Това е хибриден алгоритъм, който съчетава:

• Бързо сортиране (Quicksort) за повечето случаи
• Heap сортиране (Heapsort), ако дълбочината на рекурсията стане твърде голяма (за да се избегне най-лошият случай на Quicksort)
• Вмъкващо сортиране (Insertion Sort) за малки подмасиви

Introsort осигурява средна добра производителност на Quicksort с гаранция за най-лошия случай O(n log n), благодарение на превключването към Heapsort.

Пример за използване на 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;
}

Така std::sort е високоефективен алгоритъм, базиран на Introsort.