Qual algoritmo é implementado dentro da função std::sort em C++?

Na biblioteca padrão do C++, a função std::sort é 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) para garantir um tempo de execução pior de O(n log n), se a profundidade da recursão se tornar demasiado grande.
• Ordenação por inserção (Insertion sort) para submatrizes pequenas, o que aumenta a eficiência.

O Introsort começa com ordenação rápida, mas se a profundidade da recursão exceder um limite determinado (normalmente relacionado com o logaritmo do tamanho do array), muda para ordenação por heap para evitar a degradação do desempenho.

Isso garante um bom desempenho em média e um tempo garantido no pior caso.