Koks rūšiavimo algoritmas naudojamas funkcijoje sort?

Standartinėje C++ bibliotekos dalyje funkcija std::sort paprastai įgyvendinama naudojant Introsort (Introspektyvinį rūšiavimą) algoritmą. Tai hibridinis algoritmas, kuris jungia:

• Greitą rūšiavimą (Quicksort) daugeliu atvejų
• Heapsort (Kopų rūšiavimą), jei rekursijos gylis tampa per didelis (siekiant išvengti blogiausio Quicksort atvejo)
• Įterpimo rūšiavimą (Insertion Sort) mažiems submasyvams

Introsort užtikrina vidutiniškai gerą Quicksort našumą ir garantuoja blogiausią atvejį O(n log n), dėl perėjimo prie Heapsort.

Pavyzdys, kaip naudoti 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;
}

Todėl std::sort yra aukšto našumo algoritmas, pagrįstas Introsort.