Un $\Theta (n^2)$ qui bat un $\Theta (n\log n)$

Mesure sur des tableaux de int tirés au hasard, compilés en -O2, temps moyen par tri :

    n | insertion (us) | fusion (us) | gagnant
   48 |           0,28 |        0,55 | insertion
   64 |           0,44 |        0,75 | insertion
   80 |           0,78 |        1,03 | insertion
   96 |           1,12 |        1,28 | insertion
  112 |           1,74 |        1,65 | fusion
  128 |           2,12 |        1,85 | fusion
  256 |           7,55 |        4,32 | fusion
  512 |          28,95 |       10,18 | fusion
 4096 |        1515,30 |       117,70 | fusion
16384 |       23733,69 |       621,68 | fusion

Le tri quadratique gagne jusque vers $n\approx 100$, et le point de bascule est net. Les ordres de grandeur ne sont pourtant pas démentis : de $4096$ à $16384$, le temps du tri par insertion est multiplié par $15,7$ (on attendait $16$ pour un quadruplement de $n$), celui du tri par fusion par $5,3$ (on attendait $4\times \frac{14}{12}\approx 4,7$).

Ce que dit vraiment un $\Theta$. Écrire $T_{\text{ins}}(n)=\Theta (n^2)$ et $T_{\text{fus}}(n)=\Theta (n\log n)$, c'est affirmer l'existence de constantes $c_1,c_2$ telles que $T_{\text{ins}}\approx c_1{n}^2$ et $T_{\text{fus}}\approx c_{2}n{\log }_{2}n$. La comparaison $c_1{n}^2<c_{2}n{\log }_{2}n$ équivaut à $n/{\log }_{2}n<c_2/c_1$ : elle est vraie pour les petits $n$ dès que $c_2\gg c_1$. Or c'est le cas ici : le tri par insertion ne fait que comparer et décaler, sur des cases voisines en mémoire ; le tri par fusion appelle, alloue un tableau auxiliaire, et recopie.

La conclusion, et elle est double.

• L'ordre de grandeur reste la bonne mesure, car il décide du comportement pour les grands $n$ — et le facteur $38$ à $n=16384$ le montre. Aucune constante ne sauve un quadratique sur de grandes données.
• Il ne décide de rien en dessous du seuil de bascule. C'est pourquoi les bibliothèques de tri réelles emploient un tri par insertion sur les segments courts et basculent sur un tri récursif au-delà : elles prennent le meilleur des deux, et le seuil se mesure, il ne se devine pas.

Le chapitre l'annonçait : « un $O(n^2)$ battra un $O(n\log n)$ sur les petites entrées et perdra toujours sur les grandes ». Ici, la phrase est chiffrée.