Le tri par fusion

Fusion de deux listes triées

Le principe de la fusion.

On dispose de deux listes triées L1 et L2 (ordre croissant). On veut fusionner ces deux listes en une liste triée.

L'algorithme de fusion est le suivant :

	1. Créer une liste vide L3.
	2. Ajouter a=min(L1[0], L2[0]) en queue de L3.
	3. Effacer a de sa liste d'origine.
	4. Reprendre au point 2 jusqu'à ce que L1 ou L2 soit vide.
	5. Ajouter en queue de L3 les éléments de celle des deux listes L1, L2 qui n'est pas vide.

Remarque : dans cet algorithme, L1 et L2 peuvent être deux sous-listes d'une liste L initiale.

Un exemple

On dispose de la liste L= [3,6,8,9,10, 2,4,5]. Cette liste peut être découpée en deux-sous listes L1 et L2 triées :
L=[ 3,6,8,9,10, 2, 4, 5 ].

Déroulons les étapes de l'algorithme :
L3 = [] et L=[ 3,6,8,9,10, 2, 4, 5 ]
L3 = [2] et L=[ 3,6,8,9,10, 4, 5 ]
L3 = [2, 3] et L=[ 6,8,9,10, 4, 5 ]
L3 = [2, 3, 4 ] et L=[ 6,8,9,10, 5 ]
L3 = [2, 3, 4, 5 ] et L=[ 6,8,9,10, ]
L3 = [2, 3, 4, 5, 6,8,9,10 ] et L=[ , ]

Remarque : dans une implémentation de l'algorithme, il n'est pas nécessaire de vider la liste L. On utilisera plutôt des "indicateurs de position" (variables de type int par exemple) pour savoir où l'on en est dans chaque sous-liste. Cela évite de redéfinir L en permanence et est moins coûteux en temps de calcul.

Le tri par fusion.

Principe du tri par fusion.

L'algorithme du tri par fusion est le suivant :

Entrée : une liste  L d'éléments comparables.
Sortie : la liste triée en ordre croissant.

Traitement :
	1. lg = 1
	2. On fusionne, deux par deux, les sous-listes consécutives de L de taille lg :  L1 et L2 -- L3 et L4 -- L5 et L6 -- ...
	   (il est possible que la dernière liste n'ait pas la taille lg, ce n'est pas important).
	3. lg=lg*2
	4. On reprend au point 2 jusqu'à ce que lg > taille initiale de L.
  

Illustration.

On applique cet algorithme sur la liste L=[3, 2, 1, 5, 4, 2].

On fusionne, deux par deux, les listes de taille 1 consécutives : L=[3, 2, 1, 5, 4, 2 ]
ce qui donne : L=[2, 3, 1, 5, 2, 4 ]

On recommence avec les sous-listes de longueur 2,
L=[2, 3, 1, 5, 2, 4 ]
ce qui donne L=[1, 2, 3 , 5, 2, 4 ]

On recommence :
L=[1, 2, 3 , 5, 2, 4 ]
donne :
L=[1, 2, 2, 3, 4, 5 ]

Le principe par l'illustration

Illustration :

Illustration avec python et tkinter

Exécuter le petit programme ciblé ici.

Temps de calcul du tri par fusion.

Le nombre d'opérations d'un tri par fusion est majoré par k*n*log(n) où k est une constante (et où n désigne la taille de la liste donnée en entrée).

C'est, en un certain sens que nous ne préciserons pas plus avant ici, ce que l'on peut faire de mieux en terme de complexité pour un tri.

Le temps d'exécution, pour de grandes valeurs de n, est nettement meilleur pour un tri par fusion que pour un tri par sélection.