Tri fusion
Le tri fusion transforme un problème difficile en beaucoup de problèmes faciles : deux listes triées sont simples à combiner en une seule. Coupez la liste en deux jusqu'à ce que chaque morceau soit une seule valeur, puis fusionnez les morceaux entre eux. C'est l'algorithme « diviser pour régner » classique, et son temps est n log n quelle que soit l'entrée.
L'idée
La fusion est la partie facile. Avec deux listes déjà triées, comparez leurs premières valeurs et prenez la plus petite. Comparez les nouvelles premières valeurs et prenez encore la plus petite. Quand une liste est vide, ajoutez le reste de l'autre. Chaque étape prend une valeur, donc fusionner deux listes de longueur totale m demande au plus m − 1 comparaisons. Le tri fusion s'en sert pour trier : coupez la liste en deux, triez chaque moitié par tri fusion, et fusionnez les deux moitiés.
Un exemple
Prenons 5, 1, 4, 2, 8. On la coupe en 5, 1 et 4, 2, 8. La première moitié se coupe en 5 et 1, qui fusionnent en 1, 5. La seconde moitié se coupe en 4 et 2, 8 ; le 2, 8 est fusionné à partir de 2 et 8, puis fusionné avec 4 en 2, 4, 8. Enfin, 1, 5 et 2, 4, 8 fusionnent : 1, puis 2, puis 4, puis 5, et il reste 8. Cela fait 8 comparaisons, 12 écritures et 4 fusions.
Pourquoi n log n
Chaque découpage divise les morceaux par deux, donc après environ log₂ n niveaux, chaque morceau est une seule valeur. En remontant, chaque niveau de fusions traite chaque valeur une fois, soit n écritures et moins de n comparaisons par niveau. Au total, cela fait environ n log₂ n. Pour 40 valeurs, le tri fait 216 écritures et au plus 177 comparaisons ; le tri à bulles peut demander 780 comparaisons pour la même liste. L'ordre de l'entrée compte beaucoup moins que pour ces tris : pour 40 valeurs, une liste triée demande 100 comparaisons, une liste inversée 116, et une liste aléatoire environ 160.
Le tampon, et la stabilité
Pour fusionner deux moitiés voisines dans la liste, la méthode habituelle les copie dans un tampon et les réécrit dans l'ordre. L'application montre ce tampon comme la deuxième rangée de barres. Il faut autant de mémoire en plus que la liste : c'est le principal coût du tri fusion. En échange, le tri est stable : quand les deux valeurs de tête sont égales, celle de la moitié gauche passe en premier, donc les valeurs égales gardent leur ordre. La stabilité compte quand on trie des enregistrements selon un champ, puis un autre.
Histoire et usages
John von Neumann a décrit le tri fusion en 1945, ce qui en fait l'un des premiers algorithmes écrits pour un ordinateur à programme enregistré. Comme il lit et écrit les données par longues séquences, c'était la méthode standard pour trier des données sur bande, et il sert encore pour les fichiers trop gros pour la mémoire. Timsort, utilisé par Python et par Java pour les objets, est un tri fusion qui cherche d'abord les séquences déjà triées et utilise le tri par insertion pour les petits morceaux.
À vous d'essayer
Ouvrez l'application et appuyez sur Étape. La partie ombrée de la liste est en cours de découpage ou de fusion, et la ligne pointillée marque le milieu. Au début d'une fusion, les deux moitiés descendent dans la rangée tampon ; les deux valeurs de tête sont comparées, et la plus petite remonte. Suivez les compteurs : les écritures sont les mêmes pour toute liste de même longueur, et les comparaisons sont au plus bas pour une liste triée ou inversée et au plus haut pour une liste aléatoire, sans jamais dépasser environ n log₂ n.
Questions fréquemment posées
Quelle est la complexité en temps du tri fusion ?
O(n log n) dans le meilleur, le moyen et le pire cas. La version habituelle demande O(n) de mémoire en plus pour le tampon.
Quelle est la différence entre le tri fusion et le tri rapide ?
Les deux divisent la liste et trient les parties. Le tri fusion coupe au milieu sans regarder les valeurs et fait son travail lors de la fusion ; le tri rapide fait son travail lors du découpage, en déplaçant les valeurs autour d'un pivot, et n'a pas besoin de fusion. Le tri rapide trie sur place et est souvent plus rapide en pratique, mais il peut ralentir jusqu'à n² sur de mauvaises entrées et n'est pas stable. Le tri fusion est toujours en n log n et stable.
Qu'est-ce que le tri fusion ascendant ?
Une version sans récursion : on fusionne d'abord les valeurs voisines en paires, puis les paires en groupes de quatre, et ainsi de suite, en doublant la longueur à chaque tour. Elle fait le même travail que la version descendante montrée ici.
Le tri fusion est-il stable ?
Oui, tant qu'en cas d'égalité on prend d'abord la valeur de la moitié gauche, comme le fait cette application.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer le tri fusion