Algorithme de tri-fusion

Le tri à fusion est un algorithme de tri qui consiste à concaténer deux listes triées en une seule. Son principe s’appuie sur la méthode deviser pour régner. L'avantage de tri à fusion est que les deux listes sont fusionnées en même temps, donc on peut faire une implémentation avec les threads.

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.