bsort: A theoretically efficient non-comparison-based sorting algorithm for integer and floating-point numbers

Ce papier présente bsort, un algorithme de tri non basé sur la comparaison pour les entiers et les nombres à virgule flottante, qui atteint une complexité temporelle de $O(wn)$ et une complexité spatiale de $O(w)$ tout en offrant des performances compétitives pour les petits mots de données.

L'essentiel

🌟 Le Concept de Base : Trier sans Comparer

Imaginez que vous devez trier une immense pile de cartes à jouer.

• La méthode classique (comme std::sort) : C'est comme un jeu de "Qui a la plus grande valeur ?". Vous prenez deux cartes, vous les comparez, vous décidez laquelle est plus grande, puis vous les remettez dans l'ordre. Vous répétez cela des milliers de fois. C'est efficace, mais cela demande beaucoup de "pensée" (comparaisons) pour chaque carte.
• La méthode bsort : C'est comme trier des cartes par leur couleur, puis par leur forme, puis par leur valeur, sans jamais vraiment se demander "qui est plus grand que qui". On regarde simplement les petits détails (les bits) qui composent le nombre.

L'auteur, Benjamin Guzmán, a créé un algorithme appelé bsort qui fonctionne comme un tri par "détails successifs". C'est une méthode très rapide pour les petits nombres, mais qui a quelques défis pour les très grands.

---

🔍 Comment ça marche ? L'analogie du Tri Postal

Pour comprendre bsort, imaginez que vous êtes un facteur qui doit trier des milliers de lettres. Chaque lettre a un code-barres (le nombre) composé de petits points noirs et blancs (les bits).

1. Le tri par "Signe" (Positif ou Négatif)

Avant de regarder les chiffres, le facteur regarde d'abord si la lettre est pour le "Quartier Nord" (négatif) ou le "Quartier Sud" (positif).

• Le problème : Dans le langage des ordinateurs, les nombres négatifs sont écrits d'une manière spéciale qui les fait sembler "plus grands" que les positifs si on les lit à l'envers.
• La solution de bsort : L'algorithme fait une petite astuce. Il trie d'abord les négatifs et les positifs, mais il inverse l'ordre pour les négatifs au début, pour s'assurer que les petits nombres négatifs (comme -100) finissent bien avant les grands (comme -1). C'est comme dire : "Mettez d'abord les lettres du Nord, mais dans l'ordre inverse de leur numéro de rue !"

2. Le tri par "Exposant" (La taille du nombre)

Ensuite, pour les nombres à virgule (comme 1,5 ou 1000,2), le facteur regarde la partie qui indique la taille du nombre (l'exposant).

• Imaginez que vous séparez d'abord les lettres pour les "enfants" (petits nombres), puis les "adultes" (nombres moyens), puis les "géants" (très grands nombres).
• L'astuce : Pour les nombres négatifs, les "géants" (comme -1000) sont en fait "plus petits" que les "enfants" (comme -1). Donc, pour les négatifs, l'algorithme trie les tailles de la plus grande à la plus petite. Pour les positifs, c'est l'inverse.

3. Le tri par "Mantisse" (Le détail précis)

Enfin, une fois que les lettres sont dans les bons quartiers (négatif/positif) et les bons groupes de taille, le facteur regarde les derniers chiffres pour les ranger parfaitement. C'est comme ranger les lettres d'un même quartier par ordre alphabétique.

---

🏎️ Pourquoi c'est rapide (et pourquoi ce n'est pas toujours parfait)

✅ Les Points Forts : Le Tri des Petits Objets

L'article montre que bsort est une championne pour trier des petits objets, comme des lettres de 8 bits (des nombres de 0 à 255).

• Analogie : Si vous devez trier des pièces de monnaie de 1 centime, 2 centimes, etc., vous n'avez pas besoin de les comparer une par une. Vous pouvez simplement les jeter dans 3 boîtes (1, 2, 3) et les ranger. C'est ultra-rapide.
• Résultat : Pour les petits nombres, bsort bat souvent les méthodes classiques, car elle ne perd pas de temps à comparer "qui est plus grand".

⚠️ Les Points Faibles : Le Problème des "Grands" Objets

Pour les très grands nombres (comme les nombres à virgule flottante de 64 bits), bsort rencontre des problèmes.

• L'analogie du "Tapis roulant" : Imaginez que pour trier un grand nombre, l'algorithme doit faire passer chaque lettre sur un tapis roulant 64 fois (une fois pour chaque bit).
• Le problème : Les autres algorithmes modernes (comme ceux utilisés par Google ou C++) sont plus intelligents. Ils disent : "Ah, cette pile de lettres est petite, je vais utiliser une méthode rapide et simple pour finir". Ils arrêtent le tapis roulant tôt. bsort, lui, continue de faire passer les lettres sur le tapis jusqu'au tout dernier bit, même si ce n'est plus nécessaire.
• La conséquence : Cela crée beaucoup de "bruit" dans l'ordinateur (des erreurs de prédiction de branches) et vide la mémoire cache (le bureau de travail de l'ordinateur), ce qui le ralentit sur les gros volumes de données.

---

🎯 En Résumé : Que retenir ?

1. C'est un tri "intelligent" : Au lieu de comparer A et B, il regarde les petits détails (bits) qui composent A et B, un par un, du plus important au moins important.
2. C'est universel : Il sait trier des nombres entiers (positifs et négatifs) et des nombres à virgule (comme 3,14) en utilisant la même logique de base.
3. C'est économe : Il n'a pas besoin de beaucoup de mémoire supplémentaire. Il trie directement dans la pile de données existante, comme si vous réarrangiez des livres sur une étagère sans en sortir un seul.
4. Le verdict :
   • Pour les petits nombres (comme les codes couleurs, les âges, les petits entiers) : bsort est une fusée ! 🚀
   • Pour les très grands nombres : Il est un peu trop rigide et perd du temps à faire des allers-retours inutiles, alors que les algorithmes modernes s'adaptent mieux.

L'idée finale de l'auteur : bsort est une excellente base théorique. Si on lui ajoute un peu de "souplesse" (en arrêtant le tri tôt pour les petits groupes, comme le font les autres), il pourrait devenir l'un des meilleurs trieurs de l'univers informatique.

Résumé technique

Résumé Technique : bsort – Un algorithme de tri non basé sur la comparaison

1. Problématique

Le tri est un problème fondamental en informatique. Les algorithmes classiques de tri par comparaison (comme le tri rapide ou le tri fusion) ont une complexité temporelle inférieure bornée par $\Omega(n \log n)$. Bien que des algorithmes non basés sur la comparaison (comme le tri par base ou radix sort) offrent une complexité linéaire $O(n)$, ils présentent souvent des limitations :

• Ils nécessitent souvent un espace mémoire supplémentaire important (non in-place).
• Ils sont souvent limités aux entiers non signés.
• Le tri d'entiers signés et de nombres à virgule flottante nécessite des transformations complexes ou des approches distinctes.

L'objectif de cet article est de proposer un algorithme unique, in-place (tri sur place), capable de trier efficacement des entiers signés, des entiers non signés et des nombres à virgule flottante, tout en conservant une complexité théorique linéaire par rapport au nombre d'éléments.

2. Méthodologie

L'algorithme bsort est une extension et une unification du tri rapide binaire (binary quicksort), qui partitionne les données bit par bit, du bit le plus significatif (MSB) au moins significatif.

A. Fondements Théoriques

Le tri rapide binaire standard fonctionne bien pour les entiers non signés car l'ordre lexicographique des bits correspond à l'ordre numérique. Cependant, pour les entiers signés (complément à deux) et les nombres flottants (IEEE-754), le bit de signe (MSB) inverse l'ordre numérique (les nombres négatifs ont un MSB à 1, les positifs à 0).

B. Adaptation pour les Entiers Signés

Pour corriger l'inversion de l'ordre des nombres négatifs et positifs, bsort inverse la direction du tri lors du premier passage (sur le bit de signe).

• Mécanisme : Au lieu de placer les 0 avant les 1 (pour un tri ascendant), l'algorithme place les 1 (négatifs) avant les 0 (positifs) lors du premier partitionnement.
• Résultat : Cela rétablit l'ordre numérique correct, permettant ensuite de trier récursivement les sous-ensembles de nombres négatifs et positifs de manière standard.

C. Adaptation pour les Nombres à Virgule Flottante (IEEE-754)

L'article propose une approche en trois passes séquentielles pour les flottants, basée sur leur décomposition théorique $x = s \cdot m \cdot b^p$ (signe, mantisse, exposant) :

1. Tri par le signe ($s$) : Partitionne l'ensemble en nombres négatifs et non négatifs (en inversant la direction pour les négatifs, comme pour les entiers signés).
2. Tri par l'exposant ($p$) : Trie chaque partition par signe indépendamment.
   • Point crucial : Pour les nombres négatifs, l'ordre des exposants doit être inverse à celui des nombres positifs (car un exposant plus grand pour un nombre négatif signifie une valeur plus petite, ex: $-2^3 < -2^1$).
3. Tri par la mantisse ($m$) : Une fois le signe et l'exposant fixés, le tri par la mantisse équivaut au tri d'entiers non signés.

D. Complexité et Espace

• Complexité Temporelle : $O(w \cdot n)$, où $n$ est le nombre d'éléments et $w$ la taille du mot (en bits). Pour des types de données fixes (ex: 32 ou 64 bits), cela se comporte comme $O(n)$.
• Complexité Spatiale : $O(w)$ d'espace auxiliaire (pile de récursion). L'algorithme est in-place car il n'utilise que des échanges de variables et des pointeurs, sans allocation de tableaux auxiliaires proportionnels à $n$.

3. Contributions Clés

1. Unification : C'est le premier algorithme présenté qui traite de manière unifiée et in-place les entiers signés, non signés et les flottants via une seule procédure de partitionnement binaire modifiée.
2. Preuve de Correction : L'article fournit des preuves formelles (Théorèmes 1 à 3) démontrant que l'ordre hiérarchique (Signe $\to$ Exposant $\to$ Mantisse) est nécessaire et suffisant pour garantir la correction du tri des flottants.
3. Analyse Empirique : Une comparaison rigoureuse avec des algorithmes de l'état de l'art (Introsort/std::sort, Spreadsort, et ska_sort).

4. Résultats Expérimentaux

Les tests ont été réalisés sur un processeur Intel i5-8350U avec des jeux de données allant de $10^5$à$5 \cdot 10^9$ éléments.

• Performance sur petits mots (8 bits) : bsort surpasse systématiquement les algorithmes hybrides comme Introsort. La complexité $O(w \cdot n)$ devient très avantageuse lorsque $w$ est petit, car le facteur $w$ est négligeable par rapport au terme $\log n$ des algorithmes de comparaison.
• Performance sur grands mots (32/64 bits) : La performance relative de bsort diminue par rapport aux algorithmes hybrides.
  • Goulots d'étranglement identifiés :
    1. Prédiction de branches : Les vérifications conditionnelles dans la boucle de partitionnement sont imprévisibles sur des données aléatoires (taux d'échec de ~50%), entraînant des vidages de pipeline.
    2. Pollution de la pile et pression sur les registres : La structure récursive rigide force des basculements de contexte fréquents et une mauvaise localité des données en cache L1.
    3. Volume d'instructions : L'algorithme scanne l'ensemble du tableau $w$ fois, alors que les algorithmes hybrides (comme Introsort) réduisent la profondeur de récursion et utilisent des méthodes itératives pour les petits tableaux.

5. Signification et Perspectives

bsort démontre qu'un algorithme de tri purement non basé sur la comparaison, entièrement in-place et capable de gérer des types de données hétérogènes, est réalisable avec une complexité théorique optimale.

• Signification : Il offre une alternative mémoire-économique ($O(w)$ espace) aux tris standards, particulièrement pertinente pour les systèmes embarqués ou les environnements à mémoire limitée où l'allocation de mémoire supplémentaire est coûteuse.
• Limites actuelles : La version actuelle, bien que théoriquement efficace, souffre de contraintes micro-architecturales modernes (prédiction de branches, hiérarchie de cache) qui pénalisent sa performance sur les grands mots de données par rapport aux algorithmes hybrides optimisés.
• Travaux futurs : L'auteur suggère que l'intégration de techniques hybrides (commutation vers des méthodes itératives pour les petits tableaux), l'utilisation d'instructions SIMD (Single Instruction, Multiple Data) et l'optimisation pour éviter les branchements (branchless programming) pourraient combler l'écart de performance et libérer le potentiel théorique de l'algorithme.

En conclusion, bsort constitue une avancée conceptuelle majeure en unifiant le tri binaire pour tous les types numériques, tout en soulignant le fossé persistant entre la complexité asymptotique théorique et les performances pratiques sur l'architecture matérielle actuelle.