Exercice Algorithme : Le Tri Fusion

Travail à Faire:

Réaliser le Tri Fusion

Principe

Le principe de cet algorithme est de diviser le tableau en sous tableaux de les traiter et ensuite de les fusionner. Cet algorithme est récursif. On divise le tableau en deux sous tableaux qui sont eux mêmes sont divisés en deux sous tableaux, etc.. La condition d'arrêt est lorsque le tableau ne comporte plus qu'un seul élément.
L'algorithme contient plusieurs parties : la division du tableau en deux, le tri des deux tableaux et la fusion des deux tableaux.

Exemple:
 

Algorithme fusion (T , deb, fin)
 mid = (deb + fin)/2 ;
 i = 0 ; i1 = deb ; i2 = mid + 1 ;
 Tant que (i1 < mid et i2 < fin) Faire
 Si (T [i1] < T [i2])
 temp[i] = T [i1] ;
 i1 = i1 + 1 ;
 Sinon
 temp[i] = T [i2] ;
 i2 = i2 + 1 ;
 Fin Si
 i = i + 1 ;
 Fin Tant que
 Si (i1 < mid)
 Pour (j = i1 a mid) Faire
 temp[i] = T [j] ;
 i = i + 1 ;
 Fin Pour
 Sinon Si (i2 < fin)
 Pour (j = i2 a fin) Faire
 temp[i] = T [j] ;
 i = i + 1 ;
 Fin Pour
 Fin Si
 Pour (i = deb a fin) Faire
 T [i] = temp[i] ;
Fin Pour