¿Se puede optimizar el siguiente codigo?

[enrieto]

qsort y bsearch

¿que tan eficientes son?

Creo que es el patrón más eficiente incluido en la biblioteca estándar del C. bsearch implementa el concepto de búsqueda binaria sobre una secuencia ordenada. Información razonable acá:
https://en.wikipedia.org/wiki/Binary_search_algorithm

Me parece que la mejora que ha tenido en tiempo es brutal

Si usaras una búsqueda binaria tendrías que llegar a los milisegundos.

el único lenguaje capaz de plantar cara a C y ganarle es ASM ¿es cierto eso?

No, no lo creo; el C++ es casi siempre más eficiente que el C, y en el peor de los casos es igual. Por ejemplo, el std::sort del C++ es entre 2 o 3 veces más rápido que qsort.

Ah, me olvidaba

bsearch dice que si hay elementos duplicados el resultado es impredecible

Código C:

void *bsearch(const void *key, const void *base, size_t nel,
       size_t width, int (*compar)(const void *, const void *));
 

bseach devuelve un puntero al valor en "base" que se corresponde con la "key"; si "base" tuviera valores repetidos, bsearch va a devolver un puntero a uno de esos, que puede ser el primero en la secuencia o no, no sabremos cuál.