07 — Stabilité, tri en place, et ce que font vraiment sort() et sorted()

Ce que tu vas apprendre

• Ce que la stabilité change concrètement, avec un exemple
• Ce que veut dire « trier en place » et pourquoi c'est un compromis
• Timsort : l'algorithme réel de sorted() et Array.sort()
• Les pièges classiques quand on appelle sort()

Prérequis

• 06 — Tris linéaires
• Idéalement, les articles 03 (fusion) et 04 (rapide)

On a parcouru les algorithmes. Reste à les relier au code que tu écris vraiment, celui qui appelle array.sort() ou sorted(liste). Cet article fait la synthèse sur deux propriétés pratiques, la stabilité et le tri en place, puis révèle l'algorithme qui se cache derrière les fonctions de tri des langages courants.

La stabilité, concrètement

Un tri est stable s'il préserve l'ordre relatif des éléments égaux selon le critère de tri. Ça paraît abstrait jusqu'au moment où ça te mord. Prends une liste de commandes que tu affiches d'abord triée par date, puis que l'utilisateur retrie par montant.

typescriptconst commandes = [
  { client: "A", montant: 100, date: "01-10" },
  { client: "B", montant: 50, date: "01-09" },
  { client: "C", montant: 100, date: "01-08" },
];
// déjà trié par date, on retrie par montant
commandes.sort((a, b) => a.montant - b.montant);

Avec un tri stable, les deux commandes à 100 (A et C) gardent leur ordre par date d'avant le tri. Avec un tri instable, leur ordre pourrait s'inverser sans raison apparente, et l'utilisateur verrait un classement secondaire incohérent. La stabilité permet le tri sur plusieurs critères par tris successifs : on trie par le critère le moins prioritaire, puis par le plus prioritaire, et les égalités conservent l'ordre du tri précédent.

Récapitulatif des tris de la série :

Trier en place, un compromis

Un tri en place réorganise le tableau d'origine sans allouer de structure auxiliaire proportionnelle à la taille (O(1) ou O(log n) d'espace). C'est important quand la mémoire est rare ou quand le tableau est énorme. Mais la stabilité et le tri en place sont souvent en tension : les tris stables simples (fusion, comptage) ont besoin d'espace, et les tris en place efficaces (rapide, tas) sont instables. Obtenir les deux à la fois demande des algorithmes plus complexes. C'est précisément ce que résout Timsort.

Timsort : l'algorithme réel

Quand tu écris sorted() en Python, list.sort(), ou Array.prototype.sort() sur la plupart des moteurs JavaScript modernes (V8 depuis 2018), tu n'utilises aucun des tris « purs » de cette série. Tu utilises Timsort, un hybride conçu par Tim Peters pour Python en 2002, adopté ensuite par Java, Android et V8.

Timsort combine deux des algorithmes qu'on a vus :

• Tri par insertion sur les petits segments. L'insertion est imbattable sur quelques dizaines d'éléments, grâce à son faible surcoût. Timsort découpe d'abord le tableau en petits « runs » qu'il trie par insertion.
• Tri par fusion pour recombiner ces runs triés. La fusion est stable et garantit O(n log n).

Son astuce supplémentaire : il détecte les séquences déjà ordonnées (croissantes ou décroissantes) dans les données et les exploite telles quelles, au lieu de les retrier. Sur des données partiellement triées, un cas très fréquent en pratique, Timsort approche O(n). Il est stable, et son pire cas reste O(n log n).

C'est pour ça qu'on ne réécrit pas de tri : Timsort est le fruit de décennies de recherche, rapide sur les données réelles, stable, et déjà optimisé dans ton langage.

Les pièges quand tu appelles sort()

Connaître les algorithmes ne suffit pas, il faut aussi connaître les surprises de l'API.

Le tri lexicographique par défaut en JavaScript. [10, 2, 1].sort() renvoie [1, 10, 2]. Sans comparateur, sort() convertit les éléments en chaînes et les trie alphabétiquement. Il faut toujours fournir un comparateur pour des nombres : arr.sort((a, b) => a - b).

Le tri en place qui mute. Array.sort() modifie le tableau d'origine et le renvoie. Si tu veux garder l'original, copie d'abord : [...arr].sort(...). Python distingue les deux : list.sort() mute, sorted(list) renvoie une copie.

Le coût caché du comparateur. Le comparateur est appelé O(n log n) fois. S'il fait un calcul lourd à chaque appel (parser une date, accéder à une propriété coûteuse), le tri devient lent. La parade est le pattern « decorate-sort-undecorate » : précalculer la clé de tri une fois par élément, trier sur la clé, c'est ce que fait l'argument key= de sorted() en Python.

python# Le coût de parsing de la date est payé une fois par élément, pas à chaque comparaison
commandes_triees = sorted(commandes, key=lambda c: datetime.fromisoformat(c["date"]))

Conclusion de la série

Tu ne réécriras pas de tri en production, et c'est très bien. Mais désormais, quand sort() apparaît dans un profil de performance, tu sais que c'est du O(n log n) Timsort, pas de la magie. Quand un classement secondaire se mélange, tu penses stabilité. Quand tu tries un million d'identifiants entiers et que c'est lent, tu sais qu'un tri par comptage existe. Le tri est l'exemple parfait du métier : connaître les fondations pour mieux utiliser les outils qui les implémentent.

La suite du parcours algorithmie, la série Recherche & techniques sur tableaux, applique le même esprit à un autre problème de base : trouver vite, sans tout parcourir.

Sources

• Peters, T. (2002). listsort.txt — description de Timsort. CPython source. github.com/python/cpython/blob/main/Objects/listsort.txt
• McIlroy, P. (1993). Optimistic Sorting and Information Theoretic Complexity. SODA. (Bases théoriques des tris adaptatifs)
• V8 Team. (2018). Getting things sorted in V8. v8.dev/blog/array-sort (Adoption de Timsort dans V8)
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Section 8.1 (borne inférieure des tris par comparaison). MIT Press.