Probleme – Le tri par partition-fusion sur tableaux : coût exact et stabilité

1. Le tri.

(* Trie t par ordre croissant, en place, à l'aide d'un tampon de taille n.
   Précondition : aucune. Complexité : Theta(n log n) en temps, Theta(n) en espace.
   Le tampon est alloué UNE fois : une allocation par appel récursif ferait
   n log n allocations pour rien. *)
let tri_fusion t =
  let n = Array.length t in
  if n > 1 then begin
    let tampon = Array.make n t.(0) in
    let rec trier g d =                       (* trie t.[g .. d-1] *)
      if d - g > 1 then begin
        let m = g + (d - g) / 2 in
        trier g m; trier m d;
        let i = ref g and j = ref m and k = ref g in
        (* INVARIANT : tampon.[g .. k-1] contient, triés, les éléments déjà pris
           dans t.[g .. i-1] et t.[m .. j-1]. *)
        while !i < m && !j < d do
          if t.(!i) <= t.(!j)                 (* <= et non < : voir question 3 *)
          then begin tampon.(!k) <- t.(!i); incr i end
          else begin tampon.(!k) <- t.(!j); incr j end;
          incr k
        done;
        while !i < m do tampon.(!k) <- t.(!i); incr i; incr k done;
        while !j < d do tampon.(!k) <- t.(!j); incr j; incr k done;
        Array.blit tampon g t g (d - g)
      end
    in trier 0 n
  end

Terminaison : variant $d-g$, divisé par deux à chaque appel ; les trois boucles ont pour variant $(m-i)+(d-j)$. Correction : l'invariant écrit ci-dessus, plus le fait que les deux moitiés sont triées par hypothèse de récurrence.

2. Le coût exact.

Sur un tableau déjà trié ou parfaitement inverse, le compte vaut exactement $\frac{n}{2}{\log }_{2}n$ : à chaque fusion, l'une des deux moitiés s'épuise d'un coup et la seconde est recopiée sans comparaison. C'est le meilleur cas, et il ne vaut qu'un facteur $2$ — à comparer au tri rapide, dont le meilleur et le pire cas diffèrent d'un facteur d'ordre $n/\log n$ (problème 15.5).

La dernière colonne est une borne inférieure, et elle se démontre. Fixons un algorithme qui n'accède aux données que par comparaisons. Son exécution est entièrement déterminée par la suite des réponses obtenues : on la représente donc par un arbre binaire dont les nœuds internes sont les comparaisons et les feuilles les permutations rendues. Cet arbre a au moins $n!$ feuilles, car deux entrées demandant des réarrangements différents doivent aboutir à des feuilles différentes. Or un arbre binaire de hauteur $h$ a au plus $2^h$ feuilles, d'où $h\ge {\log }_2(n!)$. Et $n!\ge (n/2{)}^{n/2}$ donne ${\log }_2(n!)\ge \frac{n}{2}{\log }_2\frac{n}{2}=\Omega (n\log n)$.

Le cas aléatoire est à $1,9\%$ de cette borne pour $n=1024$ : le tri par partition-fusion est optimal, et il ne reste presque rien à gagner. Cela dit, la borne ne vaut que dans son modèle : un tri par comptage, qui emploie les valeurs comme indices et non par comparaison, trie $n$ entiers de $[0,k[$ en $\Theta (n+k)$ — donc en temps linéaire si $k=O(n)$. Il ne contredit rien : il n'entre pas dans le modèle. Devant une borne inférieure, la première question est toujours : dans quel modèle ?

3. La stabilité tient à un seul caractère. Le test est t.(i) <= t.(j) : en cas d'égalité, c'est l'élément de gauche qui part le premier, donc celui qui était déjà avant. Le tri est stable.

Écrire t.(i) < t.(j) le rendrait instable, sans changer ni sa complexité ni sa correction en tant que tri. C'est un exemple parfait de propriété invisible aux tests naïfs : un tableau d'entiers triés ne révèle rien. Il faut trier des couples et regarder la seconde composante.

La stabilité importe dès qu'on trie en deux passes : trier par prénom, puis par nom, ne donne des homonymes rangés par prénom que si le second tri est stable.

4. La mémoire. Le tampon coûte $\Theta (n)$, et la pile de récursion $\Theta (\log n)$. On peut fusionner deux blocs en place en $\Theta (n)$ — l'algorithme existe —, mais il est compliqué et lent en pratique. Si la mémoire est la contrainte, on prend le tri par tas du chapitre chap:tas : en place et $\Theta (n\log n)$ garanti, au prix de la stabilité et d'un accès mémoire moins régulier. Trois tris, trois compromis, aucun dominant.