Tri fusion ( merge sort)

O(nlogn) en moyenne et dans le pire des cas, stable mais pas en place.

Ce tri est un autre exemple de méthode qui applique le principe « diviser pour régner ». En effet, étant données deux suites d'éléments triés, de longueurs respectives L1 et L2, il est très facile d'obtenir une troisième suite d'éléments triés de longueur L1 + L2, par « interclassement » (ou fusion) des deux précédentes suites, comme illustré dans la procédure fusion.

Pour les besoins de la procédure triFusion, nous allons donner la forme suivante à la procédure fusion qui interclasse deux suites d'éléments placés dans un tableau tab, respectivement entre les indices debut et mil et entre les indices mil + 1 et fin :

procedure fusion(entier[] tab, entier[] tmp, entier debut, entier mil, entier fin)

   entier k;

   entier i <- debut;

   entier j <- mil + 1;

   pour (k de debut à fin en incrémentant de 1) faire

      si ((j > fin) ou (i <= mil et tab[i] < tab[j])) alors

         tmp[k] <- tab[i];

         i <- i + 1;

      sinon

         tmp[k] <- tab[j];

         j <- j + 1;

      fin si

   fin pour

   pour (k de debut à fin en incrémentant de 1) faire

   tab[k] <- tmp[k];

   fin pour

fin procedure

On constate que la procédure de fusion nécessite un tableau intermédiaire aussi grand que le nombre d'éléments à interclasser. C'est là où réside le principal inconvénient du tri fusion, car si sa complexité dans tous les cas est en O (N log N), c'est au prix d'un tableau annexe aussi grand que le tableau initial, ce qui peut se révéler handicapant dans les situations où la place mémoire est restreinte

La procédure récursive de tri fusion est alors :

procedure triFusionR(entier[] tab, entier[] tmp, entier debut, entier fin)

   si (debut < fin) alors

      entier milieu <- (debut + fin)/2;

      triFusionR(tab, tmp, debut, milieu);

      triFusionR(tab, tmp, milieu + 1, fin);

      fusion(tab, tmp, debut, milieu, fin);

   fin si

fin procedure

procedure triFusion(entier[] tab)

   entier[] tmp <- tableau de taille N;

   triFusionR(tab, tmp, 1, N);

fin procedure

La version utilisée dans l'applet de démonstration est en fait la version itérative. Elle consiste à trier des sous-suites de longueur 2, 4, ..., une puissance de 2, jusqu'à la longueur du tableau.

On obtient alors :

procedure triFusionI(entier[] tab)

   entier[] tmp <- tableau de taille N;

   entier i <- 1;

   entier debut <- 1;

   entier fin <- debut + i + i - 1;

   tant que (i < N) faire

      debut <- 1;

      tant que (debut + i -1 < N) faire

         fin <- debut + i + i - 1;

         si (fin > N) alors

            fin <- N;

         fusion(tab, tmp, debut, debut + i - 1, fin);

         debut <- debut + i + i;

      fin tant que

      i <- i + i;

   fin tant que

fin procedure