Trier, c’est remettre dans l’ordre une liste désordonnée. Le problème est omniprésent : un tableur classe ses lignes, un moteur de recherche ses résultats, un jeu vidéo ses objets du plus lointain au plus proche avant de les dessiner. Il est surtout la clé de bien d’autres problèmes : chercher par dichotomie, repérer des doublons, calculer une médiane, tout devient facile dans une liste triée. Rien d’étonnant à ce qu’on l’appelle parfois la mère de tous les problèmes algorithmiques.

Le tri par sélection est celui qu’on pratique spontanément avec des cartes étalées sur une table : chercher la plus petite, la placer en tête, puis recommencer avec les cartes restantes.
Le tri par insertion est celui du joueur qui range sa main au fur et à mesure qu’il ramasse ses cartes : chaque nouvelle carte glisse vers la gauche jusqu’à trouver sa place parmi celles déjà rangées.
Le tri à bulles, enfin, compare les voisins deux à deux et les échange s’ils sont dans le désordre : les grands éléments remontent vers la fin comme des bulles vers la surface. Il ne sert presque jamais en pratique, mais il est le plus simple à écrire.
Les trois tris reposent sur deux boucles imbriquées, et le pire cas le montre : pour une liste de $n$ éléments, on compare chaque élément à tous ceux qui le suivent, soit $(n-1)+(n-2)+\cdots+1=\dfrac{n(n-1)}{2}$ comparaisons. Les trois tris sont quadratiques : doubler la taille de la liste quadruple le travail. Ils ne se valent pourtant pas :
Combien de comparaisons le tri par insertion fait-il pour une liste de $200$ éléments rangés en ordre inverse ?
C’est son pire cas : le $i$-ème élément doit remonter jusqu’au début, au prix de $i$ comparaisons. Au total, $1+2+\cdots+199=\dfrac{200\times 199}{2}=19\,900$ comparaisons.
Pour trier un paquet de cartes, on peut le couper en deux, trier chaque moitié, puis fusionner les deux paquets triés : on compare les cartes du dessus, on prend la plus petite, et l’on recommence. La fusion ne demande qu’un seul passage. Et pour trier chaque moitié, on la coupe à son tour en deux… C’est le tri fusion, que John von Neumann décrit dès 1945, l’un des tout premiers programmes écrits pour un ordinateur à programme enregistré.
Combien coûte le tri fusion ? À chaque niveau de l’arbre des appels, les fusions traitent ensemble les $n$ éléments, pour un travail proportionnel à $n$. Et comme la taille des morceaux est divisée par deux d’un niveau au suivant, il y a $\log_2 n$ niveaux. Le coût total est de l’ordre de $n\log_2 n$ : pour un million d’éléments, une vingtaine de millions de comparaisons, contre un demi-billion pour un tri quadratique. La page Récursivité montre cet arbre, et le théorème qui généralise ce calcul.
Le tri fusion a un défaut : il n’est pas en place. Il a besoin d’une liste auxiliaire pour fusionner, donc d’une mémoire supplémentaire proportionnelle à $n$.
En 1959, Tony Hoare, jeune étudiant britannique à Moscou, travaille sur un programme de traduction automatique du russe vers l’anglais. Il doit trier les mots de chaque phrase avant de les chercher dans un dictionnaire stocké sur bande magnétique. C’est pour cela qu’il imagine Quicksort, qu’il publie à son retour en Angleterre, en 1961.
Le principe est encore de diviser pour régner, mais à l’envers du tri fusion. On choisit un élément, le pivot, et l’on range à sa gauche tous les éléments plus petits, à sa droite tous les autres : c’est la partition. Le pivot est alors à sa place définitive, et il reste à trier, indépendamment, les deux côtés. Tout le travail se fait avant les appels récursifs, et la combinaison ne coûte plus rien. Surtout, la partition se fait en échangeant des éléments à l’intérieur de la liste : Quicksort trie en place.
Des danseurs hongrois exécutent ci-dessous une variante sans hasard, où le premier élément sert toujours de pivot (chapeau noir). Le chapeau rouge passe d’élément en élément vers le pivot ; chaque fois que les deux danseurs sont dans le désordre, ils échangent leurs places. Quand le pivot récupère le chapeau rouge, il est bien placé, et chaque côté recommence.
Prendre toujours le premier élément comme pivot a un défaut grave : sur une liste déjà triée, le pivot est le plus petit élément, la partition laisse un côté vide et l’autre amputé d’un seul élément, et le tri devient quadratique. Le hasard règle le problème : avec un pivot tiré au sort, le coût moyen est de l’ordre de $n\log_2 n$ quelle que soit la liste de départ (environ $1{,}39\,n\log_2 n$ comparaisons). Il n’y a plus de mauvaise entrée, seulement de mauvais tirages, et ils sont rarissimes.
Avec le premier élément pour pivot, quelle hauteur la pile d’exécution atteint-elle pour trier une liste déjà triée de $500$ éléments ?
$500$ : chaque appel ne retire qu’un élément, le pivot, et relance le tri sur les $499$ autres. Python, qui refuse par défaut de dépasser un millier d’appels imbriqués, échouerait sur une liste triée de quelques milliers d’éléments.
Si l’on renonce à trier en place, Quicksort s’écrit en quelques lignes. Ici, il trie les lettres d’un mot : chaque appel garde la première lettre comme pivot, envoie à gauche les lettres qui viennent avant elle dans l’alphabet (ou lui sont égales), à droite les autres, et recolle les deux morceaux triés de part et d’autre du pivot.
L’élégance de ce code cache une dérobade : en fabriquant de nouvelles listes, il esquive la vraie difficulté, qui est de tout ranger à l’intérieur de la liste de départ, sans mémoire supplémentaire.
Six algorithmes trient en même temps le même tableau. À chaque instant, tous ont fait le même nombre de comparaisons ; le classement final se lit sous chaque tableau. Le type de données change tout.
Tous ces tris ont un point commun : ils n’accèdent aux éléments qu’en les comparant deux à deux. Un tel algorithme peut se dessiner comme un arbre de décision : chaque nœud est une comparaison, chaque feuille un ordre possible des éléments.
Trier trois éléments a, b, c : six ordres possibles, donc six feuilles, et trois comparaisons dans le pire cas.
Pour trier $n$ éléments, l’arbre doit pouvoir aboutir à chacun des $n!$ ordres possibles : il a au moins $n!$ feuilles. Un arbre binaire de hauteur $h$ ayant au plus $2^h$ feuilles, il faut $2^h\geqslant n!$, c’est-à-dire $h\geqslant\log_2(n!)$. Et la formule de Stirling donne $\log_2(n!)\approx n\log_2 n-1{,}44\,n$. Aucun tri par comparaisons ne peut faire mieux que de l’ordre de $n\log n$ comparaisons dans le pire cas : le tri fusion est optimal, à une petite constante près.
C’est le même argument que pour la recherche dichotomique : chaque comparaison n’apporte qu’un bit d’information, et il faut $\log_2(n!)$ bits pour désigner un ordre parmi $n!$. Pour aller plus vite, il faut, là encore, cesser de comparer.
Si les éléments sont des entiers compris entre $0$ et $m$, il suffit de compter : un tableau de $m+1$ cases reçoit le nombre d’occurrences de chaque valeur, puis on réécrit chaque valeur autant de fois qu’elle est apparue. Pas une seule comparaison, et un coût proportionnel à $n+m$ : c’est le tri par dénombrement. Il n’est intéressant que si $m$ n’est pas trop grand devant $n$.
Pour des nombres plus grands, on trie chiffre par chiffre, en commençant par les unités. Une condition est essentielle : chaque passage doit préserver l’ordre obtenu par les passages précédents entre nombres ayant le même chiffre courant. C’est le tri par base (radix sort).
Le recensement américain de 1880 a demandé près de huit ans de dépouillement. Pour celui de 1890, Herman Hollerith propose de reporter les réponses sur des cartes perforées, lues par des machines électriques : les résultats essentiels sont connus en quelques mois. Les trieuses de cartes qu’il conçoit ensuite, et toutes celles qui leur succèdent pendant un demi-siècle, trient exactement comme l’animation : une colonne de la carte à la fois, en commençant par le dernier chiffre, en distribuant les cartes dans des casiers. L’entreprise de Hollerith deviendra IBM.
Deux éléments égaux pour le tri peuvent être distincts par ailleurs : deux élèves de même note, deux fichiers de même taille. Un tri est stable s’il conserve leur ordre de départ. Dans l’animation ci-dessous, les barres blanche et noire ont la même hauteur : un tri stable ne les intervertit jamais.
Comptons les lettres « r », « c », « q » et « p » d’une phrase, rangeons les couples par ordre alphabétique, puis trions-les par effectif :
Le tri par sélection a fait passer « p » devant « c » en échangeant au loin le premier élément avec le minimum : il n’est pas stable. Le tri à bulles, qui n’échange que des voisins strictement dans le désordre, l’est. La stabilité permet de trier selon plusieurs critères : pour classer des élèves par note, puis par ordre alphabétique à note égale, on trie d’abord par nom, puis par note, avec un tri stable. C’est exactement ce que fait le tri par base, chiffre après chiffre.
| Tri | Meilleur cas | En moyenne | Pire cas | En place | Stable |
|---|---|---|---|---|---|
| sélection | $n^2$ | $n^2$ | $n^2$ | oui | non |
| insertion | $n$ | $n^2$ | $n^2$ | oui | oui |
| bulles | $n^2$ | $n^2$ | $n^2$ | oui | oui |
| fusion | $n\log n$ | $n\log n$ | $n\log n$ | non | oui |
| rapide (pivot au hasard) | $n\log n$ | $n\log n$ | $n^2$ | oui | non |
| dénombrement (valeurs de $0$ à $m$) | $n+m$ | $n+m$ | $n+m$ | non | — |
| Timsort (Python) | $n$ | $n\log n$ | $n\log n$ | non | oui |
Ordres de grandeur du nombre d'opérations, pour une liste de $n$ éléments.
Que fait sorted ? En 2002, Tim Peters écrit pour Python un tri hybride, baptisé depuis Timsort. Il repère dans la liste les tronçons déjà triés (dans un sens ou dans l’autre), allonge les plus courts par insertion, là où ce tri excelle, puis fusionne les tronçons deux à deux, en suivant des règles soigneusement choisies pour que les fusions restent équilibrées. Il est stable, et il exploite tout l’ordre déjà présent : une liste triée ne lui coûte que $n-1$ comparaisons. Java, Android, le moteur JavaScript de Chrome et bien d’autres l’ont adopté.
Pour voir Timsort exploiter l’ordre déjà présent, il suffit de compter ses comparaisons : on trie des objets dont la méthode __lt__, celle qu’appelle l’opérateur <, incrémente un compteur. Ce programme s’exécute avec le vrai Python, et donc le vrai Timsort.
Une liste déjà triée ne coûte que $n-1$ comparaisons : Timsort y voit un seul tronçon. Une liste en ordre inverse aussi : il repère un unique tronçon décroissant, qu’il retourne. Deux moitiés triées l’une après l’autre ne demandent que de repérer deux tronçons puis de les fusionner. Seule la liste au hasard s’approche de la borne $n\log_2 n$.
En 2015, une équipe de chercheurs néerlandais et allemands entreprend de prouver formellement, à l’aide d’un logiciel, que Timsort est correct. La preuve échoue : les règles qui maintiennent les fusions équilibrées ne garantissent pas toujours ce qu’elles sont censées garantir. Dans la version Java, l’erreur permettait de construire des tableaux qui faisaient planter le tri. Le correctif ne tient qu’en quelques lignes, mais il a fallu treize ans et une tentative de preuve pour le trouver.