Tri fusion
Définition : Problème : TriFusion
Entrée :
\(T\) : tableau
Sortie :
Une permutation de \(T\) triée
Fondamental : Idée de l'algorithme
À partir de deux tableaux triés, on peut reconstruire une fusion triée : le plus petit élément est soit le plus petit élément du premier tableau, soit le plus petit élément du second tableau.
Ainsi de suite, il est possible de construire un tableau trié à partir de deux tableaux triés.
Diviser : On découpe le tableau \(T\) de taille \(n\) en deux sous-tableaux T[:n/2] et T[n/2:]
Régner : On trie les sous-tableaux récursivement, ou on ne fait rien s'ils sont de taille 1.
Combiner : On calcule une permutation triée du tableau initial en fusionnant les deux sous-tableaux triés.
Simulation : Algorithme
Fonction TriFusion(T):
Si taille(T) <= 1 alors retourner T
T1, T2 <- Coupe(T)
Retourner Fusion(TriFusion(T1), TriFusion(T2))
La fonction Coupe(T) sépare un tableau \(T\) en deux sous-tableaux de taille égale à 1 près.
La fonction Fusion(T1, T2) fusionne deux sous-tableaux triés.