####
### Exerice 3 : Fusion
####

# Question 1
# On divise la liste en liste de taille 2 (récursif)
# On tri ces listes de taille 2
# On fusionne les listes au fur et a mesure

# Question 2
# 

def fusion(l1, l2):
    l = []
    i, j = (0,0)
    while i < len(l1) or j < len(l2):
        if i == len(l1):
            l.append(l2[j])
            j += 1
        elif j == len(l2):
            l.append(l1[i])
            i += 1
        elif l1[i] < l2[j]:
            l.append(l1[i])
            i += 1
        else:
            l.append(l2[j])
            j += 1
    return l

def tri_fusion(lst):
    """Renvoie une nouvelle liste avec les éléments triés (dans l'ordre croissant) de la liste d'entiers lst. """
    # à 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 fusion
        l2 = tri_fusion(lst[m:])   # l2 est la sous-liste de droite (lst[m..]) triée par fusion
        return fusion(l1, l2)

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