Qual algoritmo di ordinamento viene utilizzato nella funzione sort?

Nella libreria standard di C++, la funzione std::sort è generalmente implementata utilizzando l'algoritmo Introsort (Ordinamento introspectivo). È un algoritmo ibrido che combina:

• Quicksort per la maggior parte dei casi
• Heapsort quando la profondità di ricorsione diventa troppo grande (per evitare il caso peggiore di Quicksort)
• Insertion Sort per sottoarray di piccole dimensioni

Introsort garantisce in media buone prestazioni di Quicksort con la garanzia del caso peggiore O(n log n) grazie al passaggio a Heapsort.

Esempio di utilizzo di 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;
}

Pertanto, std::sort è un algoritmo ad alte prestazioni basato su Introsort.