¿Qué algoritmo de clasificación utiliza qsort?

No puedo encontrar ninguna información sobre qué algoritmo de clasificación C utiliza la función qsort .

¿Es rápido? No se menciona en el hombre.

La implementación de qsort no está especificada: una implementación puede usar cualquier algoritmo de clasificación. Curiosamente, el tipo no necesita ser estable, y no hay requisitos de complejidad.

La especificación completa de qsort (C11 §7.22.5.2) es la siguiente:

La función qsort

Sinopsis

 #include  void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)); 

Descripción

La función qsort ordena una matriz de objetos nmemb , cuyo elemento inicial es señalado por la base . El tamaño de cada objeto se especifica por size .

El contenido de la matriz se clasifica en orden ascendente según una función de comparación apuntada por compar, que se llama con dos argumentos que apuntan a los objetos que se comparan. La función devolverá un número entero menor que, igual o mayor que cero si se considera que el primer argumento es respectivamente menor que, igual o mayor que el segundo.

Si dos elementos se comparan como iguales, su orden en la matriz ordenada resultante no se especifica.

Devoluciones

La función qsort no devuelve ningún valor.

En teoría, qsort solo se define hasta el punto de los valores de retorno y los valores de llamada de qsort y bsort . Aquí están las referencias de la norma ISO.

En la práctica, por lo general utiliza quicksort .

Como complemento a la cita de James McNellis del estándar, vale la pena señalar que la documentación libc de GNU dice que

La función qsort deriva su nombre del hecho de que se implementó originalmente utilizando el algoritmo de “ordenación rápida”.

y que decidió utilizar un algoritmo alternativo , aparentemente una ordenación por fusión.