Comparaisons du tri fusion : pire cas et cas moyen

Il fournit le pire cas exact, l’espérance pour un ordre aléatoire uniforme, le nombre de niveaux récursifs et n multiplié par le logarithme de n en base 2 comme repère. Vous pouvez ainsi visualiser la croissance linéarithmique et la distinguer clairement d’un comportement quadratique.

Ce que le calculateur comptabilise

Le calcul porte sur les comparaisons d’ordre entre éléments pendant la fusion, opération centrale de l’analyse classique du tri fusion. Il exclut les contrôles d’indice, affectations, écritures temporaires, appels récursifs, allocations et opérations internes d’un comparateur personnalisé. Un élément seul ne demande aucune comparaison. Pour une entrée plus grande, l’algorithme divise la plage, trie les deux parties puis compare leurs premiers éléments non consommés. La fusion de groupes de a et b éléments exige au maximum a plus b moins une comparaisons, car le dernier élément restant est copié sans nouvelle comparaison. Le pire cas applique cette règle à l’arbre de découpage réel, même lorsque n n’est pas une puissance de deux. Le champ n_log2_n constitue donc un repère d’échelle, tandis que les champs de comparaison donnent les estimations opérationnelles.

Calcul du pire cas et du cas moyen

La formule exacte du pire cas vaut n fois le plafond du logarithme de n en base 2, moins deux élevé à ce plafond, plus un. Elle décrit un tri fusion binaire standard dont les sous-tableaux sont partagés aussi équitablement que possible. Le cas moyen est une espérance sur les permutations uniformément aléatoires de clés distinctes. Pour la fusion de séquences de a et b éléments, l’espérance vaut a plus b, moins a divisé par b plus un, moins b divisé par a plus un. Le calculateur additionne récursivement ces coûts sur le même arbre équilibré et n’arrondit que l’affichage final à six décimales. Une espérance peut être fractionnaire, bien que toute exécution réalise un nombre entier de comparaisons. Les doublons, une autre règle de départage, les séquences naturelles ou un seuil de tri par insertion peuvent modifier le résultat observé.

Interpréter le résultat linéarithmique

La valeur n_log2_n matérialise l’échelle linéarithmique. Chaque niveau de fusion supplémentaire traite les n éléments, alors que le nombre de niveaux ne croît que logarithmiquement. Les deux rapports divisent les estimations par n fois le logarithme de n en base 2 et indiquent leur proximité avec ce repère pour n supérieur à un. Ils restent descriptifs : ce ne sont ni des preuves de complexité ni des mesures matérielles. Les accès mémoire, allocations, caches, coûts du comparateur et environnements d’exécution peuvent dominer le temps réel. Essayez des tailles juste avant et après les puissances de deux. La profondeur récursive change à ces frontières et montre pourquoi la notation grand O masque constantes et termes inférieurs sans les rendre négligeables pour une taille précise.