¿Qué algoritmo de ordenamiento se utiliza en la función sort?

En la biblioteca estándar de C++, la función std::sort generalmente se implementa utilizando el algoritmo Introsort (Ordenamiento introspectivo). Es un algoritmo híbrido que combina:

• Ordenamiento rápido (Quicksort) para la mayoría de los casos
• Ordenamiento por montículo (Heapsort) en caso de que la profundidad de la recursión sea demasiado grande (para evitar el peor caso de Quicksort)
• Ordenamiento por inserción (Insertion Sort) para subarreglos pequeños

Introsort garantiza un buen rendimiento promedio de Quicksort con la garantía del peor caso O(n log n) gracias a la conmutación a Heapsort.

Ejemplo de uso 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;
}

Por lo tanto, std::sort es un algoritmo de alto rendimiento basado en Introsort.