Un nou algorisme quicksort en C++ ordena dades aleatòries gairebé el doble de ràpid que std::sort

blqsort, publicat amb llicència MIT, combina particions sense salts condicionals, xarxes d'ordenació per als blocs petits i una selecció robusta del pivot. Ordena 50 milions de nombres aleatoris en 0,67 segons en un Apple M1, mentre que std::sort, la funció de la biblioteca estàndard, en necessita 1,33.

blqsort és una implementació de quicksort, l'algorisme clàssic d'ordenació per comparacions, que el seu autor presenta com la més ràpida d'ús general amb dades aleatòries. Només els algorismes especialitzats que fan servir instruccions SIMD, és a dir, que processen diversos valors alhora, la superen amb tipus de dades petits. El codi és a GitHub amb llicència MIT i també inclou una versió en C, amb variants multifil, en un sol fitxer de capçalera.

En les proves de l'autor, ordenar 50 milions de doubles aleatoris va trigar 0,67 segons en un Apple M1 i 1,33 segons en un Intel i5-9300H, davant d'1,33 i 4,97 segons amb std::sort. També supera ipnsort, en la versió en C++ de ClickHouse. Segons l'autor, les versions multifil són unes tres vegades més ràpides en el M1.

El guany prové sobretot d'evitar les branques condicionals impredictibles, que obliguen el processador a buidar el pipeline quan falla la predicció de salts. Les particions petites s'ordenen amb xarxes d'ordenació, i l'algorisme detecta les dades ja ordenades, les invertides i les que tenen moltes claus repetides. Els resultats són mesures del mateix autor i no s'han verificat de manera independent.