Merge tri est un algorithme de tri populaire basé sur la comparaison connu pour son efficacité et ses performances prévisibles. Comprendre comment calculer le nombre de comparaisons qu'il fait peut aider à optimiser sa mise en œuvre et analyser ses performances dans différents scénarios.

Concept de base de fusion tri

Fusionner tri divise un tableau en sous-array plus petits, trie chaque sous-array, puis les recompile ensemble. L'opération de base consiste à comparer des éléments pendant le processus de fusion, qui détermine le nombre total de comparaisons faites.

Calcul des comparaisons pendant la fusion

Pendant l'étape de fusion, des comparaisons se produisent lors de la sélection de l'élément plus petit à partir de deux sous-arrachages triés. Pour chaque paire d'éléments comparés, une comparaison est comptée. Si les sous-arrachages ont des tailles n1 et n2, le nombre maximal de comparaisons nécessaires pour les fusionner est n1 + n2 - 1.

Estimation des comparaisons totales

Le nombre total de comparaisons dans le tri de fusion peut être approximatif en analysant chaque opération de fusion à tous les niveaux de récursion. Pour un tableau de taille n, les comparaisons totales sont approximativement:

  • n log2 n dans le cas moyen et le pire.
  • Chaque niveau de récursion implique la fusion de sous-arrachages, avec la somme des comparaisons entre tous les niveaux.
  • Le nombre de comparaisons par niveau double à mesure que les sous-réseaux augmentent.

Méthode de calcul pratique

Pour calculer les comparaisons, simulez le processus de fusion ou utilisez la relation récursive :

C(n) = C(=2=) + C(=2=) + (n - 1)

où C(n) est la comparaison totale d'un tableau de taille n. Cette formule récursive tient compte des comparaisons dans les sous-réseaux et pendant la fusion.