L'algorithme est connu pour son efficacité en complexité (temps et mémoire) et pour trier les listes :
- On coupe les données en deux parties égales.
- On trie les données de chaque partie (on découpe chaque partie, l'algorithme devient récursif).
- On fusionne les deux partie.
On devise récursivement le tableau de départ en deux sous tableaux jusqu'à ce que le tableau ne contient qu'un seul élément. Une fois que les éléments triés indépendament les uns des autres.à partir de ce moment le backtracking (Retour sur trace ) commence et on va fusionner les sous tableau en un seul jusqu'à obtenir le tableau de départ trié. La fusion consiste en des comparaison successif.
Exemple
Supposons qu'on veut trier le tableau suivant : [ 38, 27 ,43, 3, 9, 82, 10]
Algorithme
ALGORITHME TriFusion(T, gauche, droite);
T: tableau de valeurs;
gauche,droite: entier;
centre: entier;
DEBUT
SI (gauche < droite) ALORS
centre ← (gauche + droite) / 2;
TriFusion (T, gauche, centre);
TriFusion (T, centre + 1, droite);
FUSIONNER(T, gauche, centre, droite);
FSI
FIN.
Commentaires (0)
Laisser un commentaire
Connectez-vous pour commenter
Rejoignez la discussion et partagez vos connaissances avec la communauté
Chargement des commentaires...