5. Tri fusion
5.1. Spécification
On sépare le tableau en deux sous-tableaux de même taille, que l'on trie récursivement ; ensuite, on fusionne les deux sous-tableaux en gardant l'ordre (application du principe de diviser pour régner). Le cas de base correspond au tri d'un seul élément, qui ne nécessite aucune opération.
Pour la fusion des tableaux, on prend trois paramètres tels que p≤q<rp≤q<r, en sachant que les deux sous-tableaux à fusionner (A[p..q] et A[q+1..r]) sont déjà triés.
5.2. Algorithme
Tri par fusion : MergeSort(A, p, r)
Si p < r Alors
q <- round down (p+r)/2
MergeSort(A, p, q)
MergeSort(A, q + 1, r)
Merge(A, p, q, r)
Fusion de tableaux : Merge(A, p, q, r)
L[1..n1 + 1], R[1..n2 + 1] deux tableaux
n1 <- q - p + 1
n2 <- r – q
pour i <- 1 jusqu’à n1 faire
L[i] <- A[p + i - 1]
pour j ß 1 jusqu’à n2 faire
R[j] <- A[q + j]
L[n1 + 1] <- 1
R[n2 + 1] <- 1
i <- 1
j <- 1
pour k <- p jusqu’à r faire
Si L[i] <= R[j] Alors
A[k] <- L[i]
i <- i + 1
Sinon
A[k] <- R[j]
j <- j + 1