blqsort es un algoritmo de ordenación por comparación diseñado para superar a las implementaciones estándar de quicksort en datos aleatorios. Su principal ventaja radica en la eliminación de ramas condicionales (branchless partitioning) y el uso de redes de ordenación para particiones pequeñas, lo que mejora significativamente el rendimiento en arquitecturas modernas. El proyecto, disponible bajo licencia MIT en GitHub, ofrece implementaciones en C++ y C, incluyendo versiones multihilo, todas encapsuladas en un solo archivo de cabecera.
Los benchmarks realizados en sistemas Apple M1 e Intel i5-9300H demuestran su superioridad: mientras std::sort tarda 1,33 segundos en ordenar 50 millones de doubles en un M1, blqsort completa la tarea en 0,67 segundos. En sistemas con procesadores Intel, la diferencia es aún más marcada, con tiempos de 1,33 segundos frente a los 4,97 segundos de la implementación estándar. El algoritmo incluye optimizaciones específicas para entradas ya ordenadas, inversas o con muchas claves duplicadas, y utiliza la partición de Lomuto, que ofrece un comportamiento de caché más favorable que la de Hoare en CPUs actuales.
El artículo detalla cómo el uso de redes de ordenación para particiones de hasta 20 elementos permite evitar la complejidad recursiva tradicional. Además, explica la técnica de particiones sin ramas para evitar la predicción errónea del predictor de ramas, un problema crítico en la ejecución de bucles con condiciones impredecibles. Esta aproximación permite que el procesador mantenga su pipeline sin necesidad de vaciarlo constantemente, reduciendo drásticamente el tiempo de ejecución. La implementación incluye ejemplos de código en C++ y C que ilustran estas técnicas, desde la selección de pivote hasta la gestión de la recursión mediante eliminación de llamadas a cola (tail call elimination).
