Qual algoritmo de ordenação é utilizado na função sort?

Na biblioteca padrão do C++, a função std::sort é geralmente implementada usando o algoritmo Introsort (Ordenação introspectiva). É um algoritmo híbrido que combina:

• Ordenação rápida (Quicksort) para a maioria dos casos
• Ordenação por heap (Heapsort) quando a profundidade da recursão se torna muito grande (para evitar o pior caso do Quicksort)
• Ordenação por inserção para submatrizes pequenos

Introsort garante, em média, um bom desempenho do Quicksort com a garantia do pior caso O(n log n) graças à troca para Heapsort.

Exemplo 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;
}

Portanto, std::sort é um algoritmo de alto desempenho baseado em Introsort.