Fusionner deux tas : réinsérer ou reconstruire ?

Les complexités. (R) coûte $O(m\log (n+m))$ au pire : chaque insertion peut remonter jusqu'à la racine. (C) coûte $\Theta (n+m)$ : la concaténation est linéaire et le tassage de Floyd aussi (premier problème ci-après). (C) est donc asymptotiquement meilleur.

Et pourtant. Mesuré sur deux tas de $100000$ entiers tirés uniformément :

Sur les données aléatoires, la méthode asymptotiquement moins bonne gagne. La raison : dans un tas aléatoire, un élément inséré remonte en moyenne d'un nombre constant de niveaux — la moitié des places libres sont au dernier niveau, et une valeur tirée au hasard a peu de chances de battre tous ses ancêtres. L'insertion coûte $O(1)$ amorti en moyenne, et (R) devient linéaire elle aussi, avec une constante plus petite.

Le pire cas, lui, sépare les deux : en prenant pour second tas des valeurs toutes inférieures à celles du premier, chaque insertion remonte jusqu'à la racine. Mesuré : (R) passe à $865739$ comparaisons, (C) reste à $399464$ — un facteur $2,2$, et le rapport croît en $\log n$.

La leçon, et elle vaut pour tout ce chapitre. La complexité au pire est une garantie, pas une prédiction. Un algorithme qui gagne sur les données qu'on lui a montrées peut perdre d'un facteur non borné sur celles qu'on ne lui a pas montrées. On choisit (C) non parce qu'elle est plus rapide — elle ne l'est pas toujours — mais parce qu'elle est prévisible. C'est le même argument qui fera préférer le tri par tas au tri rapide sur un système temps réel.