Quel algorithme de tri est utilisé dans la fonction sort ?

Dans la bibliothèque standard de C++, la fonction std::sort est généralement implémentée en utilisant l'algorithme Introsort (Tri introspectif). C'est un algorithme hybride qui combine :

• Tri rapide (Quicksort) pour la plupart des cas
• Tri par tas (Heapsort) lorsque la profondeur de récursion devient trop grande (pour éviter le pire cas du tri rapide)
• Tri par insertion pour les petits sous-tableaux

Introsort assure en moyenne une bonne performance du tri rapide avec la garantie du pire cas O(n log n) grâce à la commutation vers le tri par tas.

Exemple d'utilisation de 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;
}

Ainsi, std::sort est un algorithme haute performance basé sur Introsort.