Le tri fusion

Algorithmique > Algorithmes de tri > Tri fusion [ Réagir ]

Principe et optimisation

Le tri fusion est un des tris qui reposent sur la devise « divide and conquer » (diviser pour régner), tout comme le tri rapide.

Comme de nombreux algorithmes de ce type, l'idée générale est de séparer le problème (le tri) en plusieurs sous-problèmes plus simples (le tri de tableaux plus petits). Il s'agit donc un algorithme récursif, même s'il est possible de l'implémenter sans utiliser de récursion (afin d'éviter de faire déborder pile).

Le principe de ce tri est le suivant : on sépare le tableau donné en une multitude de tous petits tableaux de 1 élément que l'on fusionne progressivement afin de reconstituer le tableau initial, mais trié cette fois. La véritable opération de tri se fait donc à la fusion de deux sous-tableaux. Cette fusion est très efficace puisque les deux sous-tableaux sont déjà triés.

Complexité en temps

Le tri fusion a une complexité en temps de la forme Ω(n.log(n)) dans tous les cas (même dans le pire des cas). Cette particularité le rapproche donc du du tri par tas.
En effet, le tri rapide est lui aussi en Ω(n.log(n)) mais en Ω(n²) dans le pire des cas. Il est donc moins "rapide" que le tri fusion ou le tri pas tas dans certains cas.

Conditions et évolutions

Tout comme le tri par tas et le tri rapide, le tri fusion est facilement adaptable à différentes situations.

• Pour trier autre chose que des entiers, il suffit de modifier la déclaration de TMyType.
• Pour changer la fonction de compaison, il faut adapter la fonction Compare().
  Celle-ci renvoie "TRUE" si un élément de valeur aV doit être placé avant l'élément de valeur aW dans le tableau trié.

Il ne permet cependant pas directement d'effectuer un tri en temps réel à l'insertion.

Codes sources complets

• Implémentation simple du tri fusion (Code source en Pascal publié le 2006-11-01)
  Implémentation récursive du tri fusion avec création de tableaux temporaires.