Code source du tri "fusion"
fusion(tableau T,entier premier1,entier dernier1,entier dernier2)
debut
tableau Tbis
entier premier2, compteur1, compteur2, i
premier2<-dernier1+1
compteur1<-premier1
compteur2<-premier2
taille(T)<-(dernier1-premier1+1) //taille du premier sous tableau
//on recopie dans T les éléments du premier sous tableau
pour i=premier1 à dernier1 faire
Tbis(i-premier1)<-T(i)
fin pour
//on fusionne ensuite les deux sous tableaux
pour i=premier1 à dernier2 faire
si compteur1=premier2 alors //tous les éléments du premier sous tableau ont été utilisés
arret pour //tous les éléments sont donc classés
sinon si compteur2=(dernier2+1) alors //tous les éléments du second sous tableau ont été utilisés
T(i)=Tbis(compteur1-premier1) //on recopie à la fin du tableau les éléments du premier sous tableau
compteur1<-compteur1+1
sinon si Tbis(compteur1-premier1)<T(compteur2) alors //l'élément du premier sous tableau est le plus petit
T(i)<-Tbis(compteur1-premier1) //on ajoute un élémnt du premier sous tableau
compteur1<-compteur1+1 //on progresse dans le premier sous tableau
sinon //c'est l'élément du second sous tableau qui est le plus petit
T(i)<-T(compteur2) //on recopie cette élément à la suite du tableau
compteur2<-compteur2+1 //on progresse dans le second tableau
fin si
fin pour
fin
tri_fusion_bis(tableau T,entier premier,entier dernier)
debut
entier milieu;
si premier<>dernier alors
//si l'indice du premier et du dernier élément à traiter
//est différent (condition d'arret de l'algorithme)
milieu<-(premier+dernier)/2
tri_fusion_bis(T,premier,milieu) //tri de la premiére moitiée du sous tableau
tri_fusion_bis(T,milieu+1,dernier) //tri de la seconde moitiée du sous tableau
fusion(T,premier,milieu,dernier) //fusion des deux sous moitiées
fin si
fin
tri_fusion(tableau T)
debut
entier longueur
longueur<-taille(T)
si longueur>0 alors
tri_fusion_bis(T,0,longueur-1)
fin si
fin