Motivation

Le tri Radix (Radix Sort) ne compare jamais deux nombres directement. Il les regroupe un chiffre à la fois en utilisant un tri auxiliaire stable, ce qui lui permet de franchir la barrière O(n log n) que les tris par comparaison ne peuvent pas dépasser.

Pourquoi apprendre le tri Radix ?

• Temps quasi-linéaire : il s'exécute en O(d * (n + k)) où d est le nombre de chiffres et k est la base (10 ici). Pour les nombres ayant un nombre limité de chiffres, cela revient effectivement à O(n).
• Stable : les valeurs égales conservent leur ordre relatif, ce qui est précisément ce qui permet aux passages chiffre par chiffre de se combiner correctement.
• Une idée différente : il montre que trier ne signifie pas nécessairement comparer, une perspective importante pour les entiers de grande taille ou les clés à largeur fixe.

Le compromis : il nécessite des clés que l'on peut décomposer en chiffres (ici, des entiers non négatifs) et de la mémoire supplémentaire pour les seaux (buckets).