À retenir
- Il fonctionne par récursion (il s'appelle lui-même sur des portions de plus en plus petites).
- Sa vitesse est prévisible et régulière, quel que soit l'ordre de départ des données.
- C'est un tri stable : il ne mélange pas les éléments qui ont la même valeur.
Le tri fusion est une technique de rangement de données qui repose sur la stratégie « diviser pour régner ». Pour trier une liste, l'algorithme la coupe en deux parties égales de façon répétée jusqu'à obtenir des éléments isolés, puis il les rassemble (les fusionne) deux par deux dans le bon ordre jusqu'à reconstituer la liste complète.
Étymologie
Traduction directe de l'anglais merge sort. Le terme souligne l'étape de fusion, qui est l'opération principale consistant à réunir deux ensembles déjà ordonnés pour en créer un troisième, lui aussi parfaitement trié.
Exemples d'usage
- Organiser alphabétiquement une liste d'utilisateurs dans une base de données.
- Trier un immense fichier de logs serveurs par date et heure.
- Classer des scores de joueurs du plus haut au plus bas dans un jeu vidéo.
Cas d'usage
On utilise le tri fusion lorsqu'on a besoin d'une performance stable et garantie, même sur de très gros volumes de données. Il est particulièrement apprécié pour trier des listes chaînées ou dans des contextes où l'ordre initial des éléments identiques doit absolument être préservé (tri dit « stable »).
Bonnes pratiques
Attention à la consommation de mémoire : contrairement à d'autres algorithmes, le tri fusion nécessite souvent de créer des copies temporaires des données pendant la fusion. Il est idéal pour les systèmes de fichiers externes ou les bases de données où les données ne tiennent pas toutes en mémoire vive (RAM) d'un coup.
Synonymes
Antonymes
Conseil
Pour bien le comprendre, imaginez que vous avez deux piles de cartes déjà triées devant vous. Pour les fusionner, vous n'avez qu'à regarder la carte du dessus de chaque pile, prendre la plus petite, et recommencer. C'est cette simplicité de comparaison finale qui fait toute la force de l'algorithme.
Questions fréquentes
Le tri fusion est-il le plus rapide ?
Il est très efficace pour les gros volumes, mais pour de toutes petites listes, des méthodes plus simples comme le tri par insertion peuvent être plus rapides car elles demandent moins de calculs préparatoires.
Pourquoi dit-on qu'il est stable ?
Parce que si deux éléments ont la même valeur, leur ordre relatif restera le même après le tri. C'est crucial si vous triez par nom, puis par date par exemple.