Probleme – Ce que la complexité ne dit pas : deux tris en $\Theta (n\log n)$

1. Les deux motifs.

Le tri rapide partitionne : deux curseurs partent des extrémités et progressent de proche en proche vers le milieu. Toutes les cases lues dans un tour sont voisines. Puis il récurse sur des tranches contiguës, de plus en plus petites — et dès qu'une tranche tient dans la mémoire cache, tout le sous-tri s'y fait sans accès à la mémoire principale.

Le tri par tas descend un élément de la racine vers les feuilles : de l'indice $i$ vers $2i+1$. Les indices doublent à chaque niveau. Un tassage sur un tableau de $10^6$ entiers touche successivement les indices $0$, $\sim 2$, $\sim 8$, $\sim 32$, …, $\sim 10^6$ : les derniers niveaux sont à des adresses distantes de plusieurs mégaoctets. Aucun de ces accès n'aide le suivant.

2. La prévision. Une lecture servie par le cache de premier niveau coûte quelques cycles ; un défaut de cache jusqu'à la mémoire principale en coûte deux à trois cents. Le tri par tas subit environ un défaut par niveau profond, soit ${\log }_{2}n-{\log }_2(\text{taille du cache})$ défauts par tassage. On attend donc un facteur $2$ à $3$ en faveur du tri rapide, croissant avec $n$ — puisque plus $n$ est grand, plus la part de l'arbre qui déborde du cache est grande.

3. Les mesures. Mesuré en OCaml compilé en code natif, mêmes données, même machine :

Les trois tableaux ressortent identiques, donc les trois tris sont corrects. Le tri par tas est deux fois plus lent, alors qu'il fait moins de comparaisons que le tri rapide moyen. Et sur un tableau déjà trié, où le tri rapide à pivot médian de trois est à son meilleur, l'écart monte à $3$ : $2,215$ s contre $0,696$ s à $n=5\cdot 10^6$.

Ce que la notation $O$ retient et ce qu'elle jette. Elle retient l'ordre de croissance : les deux courbes sont bien en $n\log n$, et un tri quadratique serait hors de portée à $5\cdot 10^6$. Elle jette la constante — ici un facteur $2$ à $3$ — et surtout elle jette le modèle de coût : elle suppose qu'un accès mémoire coûte $1$, ce qui est faux d'un facteur cent selon l'adresse. Le chapitre chap:algo-prog le dit ; ces trois lignes le montrent.

Alors pourquoi enseigner le tri par tas ? Pour trois raisons qu'aucune mesure ne contredit : il est $\Theta (n\log n)$ garanti, là où le tri rapide est $O(n^2)$ au pire ; il est en place, là où le tri par partition-fusion demande $\Theta (n)$ ; et il donne la file de priorité, qui sert bien au-delà du tri. On ne choisit pas un algorithme sur un chronomètre, mais sur la garantie dont on a besoin.