Le tri par fusion consiste à couper le paquet à trier en deux parts égales (ou à peu près), à trier chacun des deux demi-paquets à part, puis à rassembler les deux-demi paquets en maintenant le tout dans l'ordre.

On reconnaît ici le principe diviser pour régner :

1. Diviser : Couper le paquet en deux
2. Régner : Chaque sous paquet est trié
3. Combiner : On fusionne les deux sous-paquets triés

Cet algorithme a une complexité en $n\log_2(n)$. Si vous n'êtes pas à l'aise avec $\log_2$, dites vous simplement que c'est une fonction qui augmente de 1. Quand $n$ est multiplié par 10, $\log_2(n)$ est augmenté d'environ 3,3. Pour vous faire une idée, plus facilement voici l'évolution de $n\log_2(n)$ :

L'efficacité du tri par fusion est tout à fait remarquable.

FONCTION fusion
ENTRÉE: le tableau à trier
SORTIE: copie triée du tableau
DÉBUT
    SI tableau contient 1 élément ou moins ALORS
        RENVOYER tableau
    SINON
       COUPER tableau en deux tableaux A et B de même taille (autant que possible)
       Tri de A : A' = fusion(A)
       Tri de B : B' = fusion(B)
       fusionner les tableau A' et B'
       RENVOYER le résultat de la fusion
   FIN SI
FIN

Fusionner est le dernier élément à problème. Voici un exemple pour vous faire une idée de ce qu'il faut faire.

A' = [4, 7, 15, 26, 33] et B' = [9, 11, 28, 47] et Fusion = []

On place des curseurs en tête de tableaux A' et B', on relève celui des nombres désignés qui est le plus petit, on l'insère dans Fusion et on avance le curseur correspondant.

• A' = [4, 7, 15, 26, 33] et B' = [9, 11, 28, 47] → 4 dans Fusion → Fusion = [4]
• A' = [4, 7, 15, 26, 33] et B' = [9, 11, 28, 47] → 7 dans Fusion → Fusion = [4, 7]
• A' = [4, 7, 15, 26, 33] et B' = [9, 11, 28, 47] → 9 dans Fusion → Fusion = [4, 7, 9]
• A' = [4, 7, 15, 26, 33] et B' = [9, 11, 28, 47] → 11 dans Fusion → Fusion = [4, 7, 9, 11]
• A' = [4, 7, 15, 26, 33] et B' = [9, 11, 28, 47] → 15 dans Fusion → Fusion = [4, 7, 9, 11, 15]
• A' = [4, 7, 15, 26, 33] et B' = [9, 11, 28, 47] → 26 dans Fusion → Fusion = [4, 7, 9, 11, 15, 26]
• A' = [4, 7, 15, 26, 33] et B' = [9, 11, 28, 47] → 28 dans Fusion → Fusion = [4, 7, 9, 11, 15, 26, 28]
• A' = [4, 7, 15, 26, 33] et B' = [9, 11, 28, 47] → 33 dans Fusion → Fusion = [4, 7, 9, 11, 15, 26, 28, 33]
• A' = [4, 7, 15, 26, 33] et B' = [9, 11, 28, 47] → 47 dans Fusion → Fusion = [4, 7, 9, 11, 15, 26, 28, 33, 47]

Lors de la dernière étape, 47 n'est comparé avec rien puisqu'on a déjà inséré dans Fusion tous les éléments de A'.

Justifiez que l'algorithme de tri par fusion termine toujours.

1. Dans un fichier tri_fusion.py, donnez l'implémentation en Python de la fonction fusionner(A,B) qui fusionne les tableaux A et B comme dans l'exemple ci-dessus.
2. Dans le même fichier, donnez l'implémentation en Python de la fonction tri_fusion(tableau) en utilisant la fonction fusion et l'algorithme donné plus haut.