Welke sorteeralgoritme wordt gebruikt in de functie sort?

In de standaardbibliotheek van C++ wordt de functie std::sort meestal geïmplementeerd met behulp van het Introsort-algoritme (Introspectieve Sortering). Dit is een hybride algoritme dat het volgende combineert:

• Quicksort voor de meeste gevallen
• Heapsort wanneer de diepte van de recursie te groot wordt (om het ergste geval van Quicksort te voorkomen)
• Insertion Sort voor kleine subarrays

Introsort zorgt gemiddeld voor goede prestaties van Quicksort met de garantie van het slechtste geval O(n log n), dankzij de overschakeling naar Heapsort.

Voorbeeld van het gebruik van 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;
}

Dus, std::sort is een hoogpresterend algoritme gebaseerd op Introsort.