Stabilité du tri : ce qu'elle garantit et quand elle compte

Ce que c'est

Un tri est stable lorsque les éléments considérés égaux conservent leur ordre relatif d'entrée. Le guide de tri de Python indique que ses tris sont garantis stables. MDN note que depuis ECMAScript 2019, la spécification exige que Array.prototype.sort soit stable. Le paquet sort de Go documente Stable comme conservant l'ordre d'origine des éléments égaux, séparément de Sort, dont la stabilité n'est pas garantie. GNU sort dispose de --stable, qui désactive sa comparaison de dernier recours sur la ligne entière. La stabilité est une propriété de l'algorithme : le tri fusion, le tri par insertion et Timsort sont stables ; un simple tri rapide (quicksort) ou un tri par tas (heapsort) ne le sont pas.

Pourquoi c'est important

La stabilité permet de composer des tris. Trier par date puis, de façon stable, par statut donne des lignes regroupées par statut avec les dates en ordre à l'intérieur de chaque groupe. Un tableau triable qui se retrie à chaque clic conserve l'ordre précédent entre éléments à égalité au lieu de les mélanger. Le cas inverse est SQL : un ORDER BY sur une colonne non unique ne garantit rien pour les égalités, si bien qu'une pagination peut afficher une ligne deux fois ou jamais, sauf à ajouter une colonne de départage unique.

Comment l'appliquer

• Pour les tris multi-clés, préférer une seule clé composite (key=lambda r: (r.status, r.date)) : une seule passe, et l'intention reste visible. Des tris stables successifs, de la clé la moins significative à la plus significative, constituent l'alternative lorsque les clés nécessitent des directions différentes.
• En SQL, terminer chaque ORDER BY utilisé pour la pagination par une colonne unique (ORDER BY created_at, id).
• Ne s'appuyer sur la stabilité que là où la documentation l'affirme explicitement ; chercher le mot dans la référence de la bibliothèque avant d'en dépendre.
• Le paramètre reverse=True de Python conserve les éléments égaux dans leur ordre d'origine, ce qui diffère du fait de trier puis d'inverser la liste.
• En ligne de commande, ajouter -s à GNU sort lorsque les égalités doivent conserver l'ordre du fichier, par exemple pour trier un journal sur un seul champ.

Pièges

Les tests qui comparent une sortie triée contenant des égalités dépendent à la fois de la stabilité et de l'ordre d'entrée ; rendre les données attendues exemptes d'égalités ou trier avec une clé complète. Le classement selon la locale (LC_ALL) change l'ordre d'une même entrée d'une machine à l'autre, donc fixer la locale dans les scripts. Les algorithmes stables peuvent nécessiter de la mémoire supplémentaire (tampons de fusion), ce qui compte pour de très grands tableaux en mémoire. La stabilité ne dit rien de la cohérence de la fonction de comparaison : un comparateur incohérent produit un ordre indéfini dans n'importe quel algorithme.