blqsort es una implementación de quicksort sin saltos condicionales (branchless) escrita en C y C++ que aprovecha redes de ordenación para clasificar pequeños subconjuntos de datos. El proyecto, distribuido en GitHub como biblioteca de cabecera única, está dirigido a desarrolladores que necesitan rutinas de ordenación de alto rendimiento en aplicaciones donde el coste de las predicciones de rama erróneas en la CPU penaliza el rendimiento de algoritmos como std::sort o pdqsort.
La técnica central es el particionado branchless mediante un búfer auxiliar. En lugar de comparar y mover elementos con un 'if' tradicional, que puede detener el pipeline cuando la CPU predice mal la rama, la implementación copia 1024 elementos a una pila interna y, a continuación, alterna bloques de 1024 hacia la izquierda y la derecha, incrementando el puntero correspondiente solo si se cumple la comparación. Aunque esto duplica el número de operaciones de copia, la reducción de fallos de predicción compensa con creces para tipos de datos baratos de copiar.
Para conjuntos de 2 a 12 elementos, blqsort emplea redes de ordenación especializadas, con un camino de código independiente para cada tamaño que reduce los intercambios a unos pocos y usa una primitiva de ordenación de 2 elementos sin ramas. Para evitar el caso peor O(n²) del quicksort clásico, el algoritmo aplica la estrategia de mediana de medianas en particiones grandes, detecta desequilibrios y conmuta a heapsort en la zona afectada, y comprueba si una partición ya está ordenada. En tipos con mayor coste de copia no trivialmente copiables, como cadenas, recurre a una variante de BlockQuicksort de Edelkamp y Weiß.
En las pruebas publicadas —ordenación de 50 millones de doubles en un Apple M1 con Clang y en un AMD Ryzen con GCC, ambos con -O3— blqsort en versión monohilo tarda 0,97 s en el M1 y 2,06 s en el Ryzen, frente a 1,33 s y 5,56 s de std::sort y 1,33 s y 2,81 s de pdqsort. Con estructuras personalizadas, la diferencia se amplía: 0,96 s frente a 3,46 s en el M1.
La biblioteca se usa igual que std::sort: basta con incluir blqs.h en C++ o definir el tipo y la comparación con macros en C. Existen también variantes multihilo basadas en C++ threads y pthreads. Su principal limitación es que el enfoque con búfer resulta menos eficiente con tipos grandes o no trivialmente copiables.