descending - ¿Qué algoritmos utilizan los compiladores de C++ populares para std:: sort y std:: stable_sort?
sorting algorithms complexity (2)
Si tomamos gcc como ejemplo, vemos que es introsort para std::sort y mergesort para std::stable_sort .
Si recorre el código libc ++ , verá que también utiliza mergesort para std::stable_sort si el rango es lo suficientemente grande.
Algo que también debe tener en cuenta es que si bien el enfoque general es siempre uno de los mencionados anteriormente, todos están altamente optimizados para varios casos especiales.
¿Qué algoritmos utilizan los compiladores de C ++ populares para std :: sort y std :: stable_sort? Sé que el estándar solo da ciertos requisitos de rendimiento, pero me gustaría saber qué algoritmos usan las implementaciones populares en la práctica.
La respuesta sería más útil si citara referencias para cada implementación.
En primer lugar: los compiladores no proporcionan ninguna implementación de std::sort . Si bien tradicionalmente cada compilador viene preempaquetado con una implementación de la biblioteca estándar (que se basa en gran medida en las funciones integradas de los compiladores), en teoría podría intercambiar una implementación por otra. Un muy buen ejemplo es que Clang compila tanto libstdc ++ (tradicionalmente empaquetado con gcc) como libc ++ (completamente nuevo).
Ahora que esto está fuera del camino ...
std::sort se ha implementado tradicionalmente como una ordenación inicial . Desde un punto de vista de alto nivel, significa una implementación de clasificación rápida relativamente estándar (con un sondeo mediano para evitar un caso más desfavorable O (n 2 )) junto con una rutina de clasificación de inserción para entradas pequeñas. Sin embargo, la implementación de libc ++ es ligeramente diferente y más cercana a TimSort: detecta las secuencias ya ordenadas en las entradas y evita que se vuelvan a ordenar, lo que lleva a un comportamiento O (n) en la entrada completamente ordenada. También utiliza redes de clasificación optimizadas para entradas pequeñas.
std::stable_sort por otro lado es más complicado por naturaleza. Esto se puede extrapolar de la misma redacción de la Norma: la complejidad es O (n log n) si se puede asignar suficiente memoria adicional (insinúa una ordenación de combinación ), pero degenera a O (n log 2 n) si no.