Tri par fusion (MergeSort)

Définition

Ce tri est basé sur la technique algorithmique diviser pour régner. L'opération principale de l'algorithme est la fusion, qui consiste à réunir deux listes triées en une seule. L'efficacité de l'algorithme vient du fait que deux listes triées peuvent être fusionnées en temps linéaire.

L'algorithme de tri par fusion est construit suivant le paradigme « diviser pour régner » :[1]

  1. Diviser : on divise la séquence de 𝑛 éléments à trier en deux sous-séquences de 𝑛 éléments (𝑇[1, . . 𝑛2] 𝑒𝑡 𝑇[𝑛2+ 1, . . 𝑛]),

  2. Régner :

    • On trie les deux sous-séquences à l'aide du tri par fusion (appel récursif),

    • Toute séquence de longueur 1 est triée (donc on ne fait rien).

  3. Combiner : on combine, en les fusionnant, les deux sous-séquences triées pour produire la séquence complète triée.

Algorithme : il nous faut donc :

  • une fonction qui fusionne deux sections contiguës du tableau.

  • une fonction de tri proprement dit qui lance des appels récursifs sur les sous-parties puis appelle la fonction précédente

En pseudo-code, l'algorithme pourrait s'écrire ainsi :

1
fonction scinder(liste0) :
2
 si longueur(liste0) <= 1, renvoyer le couple (liste0, liste_vide)
3
 sinon
4
 soient e1 et e2 les deux premiers éléments de liste0, et reste le reste de liste0
5
 soit (liste1, liste2) = scinder(reste)
6
 renvoyer le couple de listes (liste de tête : e1 et de queue : liste1, liste de tête : e2 et de queue : liste2)
7
8
fonction fusionner(liste1, liste2) :
9
 si la liste1 est vide, renvoyer liste2 
10
sinon si la liste2 est vide, renvoyer liste1
11
 sinon
12
 si tête(liste1) <= tête(liste2), renvoyer la liste de tête : tête(liste1) et de queue :
13
fusionner(queue(liste1),liste2)
14
 sinon, renvoyer la liste de tête : tête(liste2) et de queue : fusionner(liste1,queue(liste2))
15
16
fonction triFusion(liste0) :
17
 si longueur(liste0) <= 1, renvoyer liste0
18
 sinon,
19
 soit (liste1, liste2) = scinder(liste0)
20
 renvoyer fusionner(triFusion(liste1), triFusion(liste2))

Exemple : 𝑇 = [38,27,43,3,9,82,10]. L'arbre de récursion explicite le principe de division (D) et de fusionnement (F) de l'algorithme.

. Exemple de Tri par fusion appliqué à un tableau de 7 éléments.