Welcher Sortieralgorithmus wird in der Funktion sort verwendet?

In der Standardbibliothek von C++ ist die Funktion std::sort in der Regel mit dem Introsort-Algorithmus (Introspektionssortierung) implementiert. Es ist ein hybrider Algorithmus, der:

• Quicksort für die meisten Fälle
• Heapsort, wenn die Rekursionstiefe zu groß wird (um den schlimmsten Fall von Quicksort zu vermeiden)
• Insertionsort für kleine Teilarrays

Introsort sorgt im Durchschnitt für eine gute Leistung von Quicksort mit der Garantie des schlimmsten Falls O(n log n), dank des Wechsels zu Heapsort.

Beispiel für die Verwendung von 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;
}

Daher ist std::sort ein leistungsstarker Algorithmus, der auf Introsort basiert.