Probleme – Le tri par partition-fusion, et la troisième récurrence

1. Le tri.

(* coupe l renvoie deux listes dont la reunion est l, de longueurs
   egales a une unite pres. Complexite : Theta(|l|). *)
let rec coupe = function
  | [] -> ([], [])
  | [x] -> ([x], [])
  | x :: y :: r -> let (a, b) = coupe r in (x :: a, y :: b)

(* fusion a b : si a et b sont triees, renvoie la liste triee de leurs
   elements reunis (avec repetitions). Complexite : Theta(|a| + |b|). *)
let rec fusion a b = match a, b with
  | [], l | l, [] -> l
  | x :: r, y :: s -> if x <= y then x :: fusion r b else y :: fusion a s

(* tri l renvoie la liste des elements de l, triee par ordre croissant. *)
let rec tri = function
  | ([] | [_]) as l -> l
  | l -> let (a, b) = coupe l in fusion (tri a) (tri b)

Vérification : coupe [3;1;4;1;5;9;2;6] rend ([3;4;5;2], [1;1;9;6]) — un élément sur deux — et tri [3;1;4;1;5;9;2;6] rend [1;1;2;3;4;5;6;9] en $16$ comparaisons.

2. Les preuves.

Terminaison de tri. Variant : la longueur $n$ de la liste. Le cas récursif ne se produit que si $n\ge 2$, et coupe rend alors deux listes de longueurs $\lceil n/2\rceil$ et $\lfloor n/2\rfloor$, toutes deux strictement inférieures à $n$ — c'est là que la garde $n\ge 2$ est indispensable : pour $n=1$, coupe rendrait $([x],[])$ et le variant ne décroîtrait pas.

Correction de fusion, par récurrence forte sur $|a|+|b|$. Si l'une des listes est vide, l'autre est triée et contient exactement les éléments à rendre. Sinon, $a=x::r$ et $b=y::s$ ; supposons $x\le y$. Comme $a$ est triée, $x$ minore $a$ ; comme $b$ est triée et $x\le y$, $x$ minore aussi $b$. Donc $x$ est un minimum de la réunion, et le placer en tête est correct pourvu que la suite le soit : c'est l'hypothèse de récurrence appliquée à $(r,b)$, dont la somme des longueurs a diminué de $1$. Le cas $x>y$ est symétrique.

Correction de tri, par récurrence forte sur $n$ : les deux moitiés sont triées par hypothèse, et fusion rend alors la réunion triée.

3. La récurrence, résolue à la main. Poser $n=2^k$. Le coût vérifie $T(n)=2T(n/2)+cn$ avec $T(1)=O(1)$. On déroule niveau par niveau : au niveau $j$, il y a $2^j$ appels portant chacun sur $n/2^j$ éléments, et la fusion de chacun coûte $cn/2^j$. Le coût du niveau $j$ vaut donc

$$2^j\times c\frac{n}{2^j}=cn,$$

indépendamment de $j$. Il y a $k={\log }_{2}n$ niveaux avant d'atteindre les listes à un élément, d'où

$$T(n)=\sum _{j=0}^{{\log }_{2}n}cn=cn({\log }_{2}n+1)=\Theta (n\log n).$$

C'est le calcul que la figure du cours fait en empilant des rectangles de même aire, et c'est tout ce qu'il faut : aucun théorème-maître.

4. La confrontation à la borne inférieure. Un tri par comparaisons doit distinguer les $n!$ permutations possibles ; chaque comparaison rend un bit ; il en faut donc au moins ${\log }_2(n!)$. Mesuré, sur des listes aléatoires :

n :               10     100     1000     10000     100000
comparaisons :    24     550     8743    120396    1536335
n log2 n :        33     664     9966    132877    1660964
log2(n!) :        22     525     8529    118458    1516704

Le tri par partition-fusion fait $1,3\%$ de comparaisons de plus que le minimum absolu à $n=10^5$. Il n'est pas seulement d'ordre optimal : il est presque optimal en constante. C'est ce qui explique sa place centrale, et le chapitre chap:diviser y reviendra pour montrer que la même récurrence gouverne toute une famille d'algorithmes.

Une réserve honnête. Sur les listes, coupe et fusion allouent $\Theta (n)$ maillons par niveau, soit $\Theta (n\log n)$ allocations au total, et la version présentée de fusion n'est pas terminale — donc $\Theta (n)$ en pile. Sur un tableau, le même tri se fait avec un seul tampon auxiliaire de taille $n$.