####
### Exercice 2 : Tri fusion
####

# Question 1
# On découpe le problème en sous preblème de même nature. La liste à trier est diviser en deux listes à trier, et ainsi de suite de façon récursive, jusqu'a arrivé a des listes de taille 1.
# On fusion et trie ensuite les listes, c'est la phase régner et combiner.

# Question 2
# Les appels récursifs se font sur la partie du graphe pour laquelle les liste sont de plus en plus petite, jusqu'a obtenir une taille 1
# Les fusions se font dans la partie basse du graphe

# Question 3

def tri_fusion(lst):
    """Renvoie une nouvelle liste avec les éléments triés (dans l'ordre croissant) de la """
    # à compléter
    if len(lst) <= 1 :
        return lst
    else:
        m = len(lst)//2             # m est la position médiane
        l1 = tri_fusion(lst[:m])    # l1 est la sous-liste de gauche (lst[0...m-1]) triée par
        l2 = tri_fusion(lst[m:])    # l2 est la sous-liste de droite (lst[m..]) triée par fusi
        return fusion(l1, l2)

# Question 4
# On peut ajouter print(lst) au début de tri_fusion pour obtenir ce résultat
[38, 27, 43, 3, 9, 82, 10]
[38, 27, 43]
[38]
[27, 43]
[27]
[43]
[3, 9, 82, 10]
[3, 9]
[3]
[9]
[82, 10]
[82]
[10]

# Question 5

def fusion(l1, l2):
    """Renvoie une liste triée résultant de la fusion des listes triées l1 et l2."""
    L = [] # création de la liste à renvoyer
    n1, n2 = len(l1), len(l2) # tailles des deux listes
    i1, i2 = 0, 0 # positions de départ dans les deux listes
    # à compléter
    while i1 < n1 and i2 < n2 :
        if l1[i1] < l2[i2]:
            L.append(l1[i1])
            i1 += 1
        else:
            L.append(l2[i2])
            i2 += 1
    for i in range(i1, n1):
        L.append(l1[i])
    for i in range(i2, n2):
        L.append(l2[i])
    return L

print(tri_fusion([38, 27, 43, 3, 9, 82, 10]))