Tri par fusion

En appliquant la méthode << diviser pour régner >> au problème du tri d'un tableau, on obtient facilement le tri par fusion (en anglais, mergesort) : on divise une table de longueur n en deux tables de longueur n/2, on trie, récursivement, ces deux tables, puis on fusionne les tables triées. Comme la fusion de deux tables ordonnées de longueur n/2 se fait en $\Theta(n)$, l'équation de complexité est $T(n) = 2T(n/2) + \Theta(n)$, dont la solution est en $\Theta(n\log n)$. Ce tri est implémenté dans les fonctions Collections.sort(List l) et Arrays.sort(Object[] t) de l'API, pour trier respectivement des listes et des tableaux d'objets. Voici une version optimisée de ce tri. Pour trier un tableau t, on commence par en créer une copie c, puis on appelle la fonction récursive triFusion() qui écrit dans t le résultat du tri de c ; chaque invocation récursive échange le rôle des tableaux source et destination :

  static void triFusion(Object[] t) {
    Object[] copie = (Object[])t.clone();
    triFusion(copie, t, 0, t.length);
  }

  static void triFusion(Object source[], Object destination[],
                        int début, int fin) {
    int longueur = fin - début;
    
    if (longueur <= 1) return;
    else {
      int milieu = (début + fin)/2;
      triFusion(destination, source, début, milieu);
      // source est trié de début à milieu
      triFusion(destination, source, milieu, fin);
      // source est trié de milieu à fin
      
      // Fusion des tableaux triés dans destination
      for (int i = début, p = début, q = milieu; 
           i < fin; 
           i++) {
        if (q>=fin || p<milieu && 
            ((Comparable)source[p]).compareTo(source[q])<=0) {
          destination[i] = source[p];
          p++;
        } else {
          destination[i] = source[q];
          q++;
        }
      }
    // destination est trié de debut à fin
    }
  }

Outre sa complexité en $\Theta(n\log n)$, le tri par fusion a l'avantage d'être stable, c'est-à-dire que des éléments de même clé ne sont pas échangés. Ceci permet de trier successivement un tableau selon plusieurs clés et de conserver l'ordre obtenu lors des tris précédents.