"""
Programme qui effectue un tri selon
l'algorithme de tri par fusion
"""

# definition de la liste qu'on veut trier
liste = [70, 50, 30, 10, 20, 40, 60]

# fonction tri_fusion qui va s'appeller elle-même
# On appelle ça une fonction récursive
def tri_fusion(liste):
    if len(liste) <= 1:
        return liste
    milieu = len(liste)//2
    liste_gauche_triee = tri_fusion(liste[:milieu])
    liste_droite_triee = tri_fusion(liste[milieu:])
    reponse = fusion(liste_gauche_triee, liste_droite_triee)
    return reponse

# fonction qui fusionne deux listes triées
# en une seule liste triée elle aussi
def fusion(liste1_triee, liste2_triee):
    i = 0
    j = 0
    liste_triee = []
    while i < len(liste1_triee) and j < len(liste2_triee):
        if liste1_triee[i] < liste2_triee[j]:
            liste_triee.append(liste1_triee[i])
            i += 1
        else:
            liste_triee.append(liste2_triee[j])
            j += 1
    if i < len(liste1_triee):
        liste_triee += liste1_triee[i:]
    else:
        liste_triee += liste2_triee[j:]
    return liste_triee

# Utilisation de la fonction tri_fusion
# pour trier la liste puis affichage
print("Voici la liste triée:")
print(tri_fusion(liste))