Milyen rendezési algoritmust használ a sort függvény?

A C++ szabványos könyvtárában a std::sort függvény általában az Introsort (Introspektív Rendezés) algoritmust használja. Ez egy hibrid algoritmus, amely ötvözi:

• Gyorsrendezést (Quicksort) a legtöbb esetben
• Heap-rendezést (Heapsort), ha a rekurzió mélysége túl nagy lesz (hogy elkerüljük a gyorsrendezés legrosszabb esetét)
• Beszúrásos rendezést (Insertion Sort) kis részhalmazok esetén

Az Introsort átlagosan jó teljesítményt nyújt a gyorsrendezésnél, és a legrosszabb esetben garantálja az O(n log n) időt, köszönhetően a heap-re váltásnak.

A std::sort használatának példája:

#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;
}

Ezért a std::sort egy magas teljesítményű, Introsort-alapú algoritmus.