def tri_fusion(liste):
    # Condition de sortie : liste déjà triée
    if len(liste) <= 1:
        return liste

    # Diviser la liste en deux moitiés
    milieu = len(liste) // 2
    gauche = liste[:milieu]
    droite = liste[milieu:]

    # Appeler récursivement tri_fusion sur chaque moitié
    gauche_triee = tri_fusion(gauche)
    droite_triee = tri_fusion(droite)

    # fusion les deux moitiés triées
    return fusion(gauche_triee, droite_triee)

def fusion(gauche, droite):
    """
    fusionne deux listes triées (gauche et droite) en une seule liste triée.
    """
    resultat = []
    i = 0
    j = 0

    # Comparer les éléments des deux listes et ajouter le plus petit au résultat
    while i < len(gauche) and j < len(droite):
        if gauche[i] < droite[j]:
            resultat.append(gauche[i])
            i += 1
        else:
            resultat.append(droite[j])
            j += 1

    # Ajouter les éléments restants de chaque liste (si l'autre est déjà vide)
    resultat = resultat + gauche[i:]
    resultat = resultat + droite[j:]

    return resultat

# Exemple d'utilisation
ma_liste = [34, 7, 12, 6, 89, 21, 1]
liste_triee = tri_fusion(ma_liste)
print("Liste originale : ", ma_liste)
print("Liste triée : ", liste_triee)