Time and Space Complexity

Complexité temporelle :

• Cas le meilleur, moyen et le pire : O(n log n)
  • Le tableau est divisé en deux environ log n fois, et chaque niveau effectue un travail de O(n) pour la fusion. Le temps d'exécution ne dépend pas de l'ordre d'entrée.

Complexité spatiale :

• O(n)
  • Contrairement aux tris sur place, le tri fusion (Merge Sort) construit de nouveaux tableaux lors de la fusion, il nécessite donc une mémoire supplémentaire proportionnelle à la taille de l'entrée.

Résumé :

• Le tri fusion est rapide et prévisible : O(n log n) dans tous les cas.
• Il est stable, donc les éléments égaux conservent leur ordre.
• Le compromis est la mémoire supplémentaire O(n) qu'il utilise pour la fusion.