Le tri fusion est un algorithme de tri asymptotiquement optimal (complexité en T(nlogn) et consomme T(n) en mémoire).

Le tri repose sur le fait que pour fusionner deux listes/tableaux trié(e)s dont la somme des longueurs est n, n-1 comparaisons au maximum sont nécessaires.

Cet algorithme n'opère pas en place : il a besoin d'une zone temporaire de données de même taille que les données ; par ailleurs, pour des données en mémoire vive, il est en pratique sensiblement plus lent que d'autres algorithmes asymptotiquement optimaux comme le tri par tas

En C :

typedef int tab_entiers[MAX];
 
void fusion

(tab_entiers t, tab_entiers tmp, int de1, int vers1, int de2, int vers2, int count, int posInB) 
{
       int i;
       for(i = 0 ; i < count ; i++)
       {
               if(de2 > vers2) 
                       tmp[posInB++] = t[de1++];
               else if(de1 > vers1) 
                       tmp[posInB++] = t[de2++];
               else if(t[de1] <= t[de2]) 
                       tmp[posInB++] = t[de1++];
               else 
                       tmp[posInB++] = t[de2++];
       }
}
 
void trifusion(tab_entiers t)
{
       tab_entiers tmp;
       int sortLength = 1, de1, de2, de3, i;
       while(sortLength < MAX)
       {
               de1 = 0;
               while(de1 < MAX)
               {
                       de2 = de1 + sortLength;
                       de3 = de2 + sortLength;
                       if(de2>MAX) de2 = MAX;
                       if(de3>MAX) de3 = MAX;
                       fusion(t, tmp, de1, de2-1, de2, de3-1, de3-de1, de1);
                       de1 = de3;
               }
 
               for(i = 0 ; i < MAX ; i++) t[i] = tmp[i];
               sortLength *= 2;
       }