Le tri fusion est un autre algorithme de tri. Celui-ci présente l’avantage d’utiliser la méthode Diviser pour Regner.

Les étapes 1 et 2 de la méthode Diviser pour Regner consistent à diviser la liste en 2 sous-listes, de manière recursive, jusqu’à obtenir des listes de 1 élément.

Le tri fusion est réalisé par la fonction fusion suivante:

def fusion(L):
    if len(L) <=1:
        return L
    m = len(L)//2
    gauche = fusion(L[:m])
    droite = fusion(L[m:])
    return interclassement(gauche,droite)

L’étape 3, enfin consiste à interclasser les sous-listes deux à deux. Compléter le code de la fonction interclassement