Le tri fusion

Le tri dit par "fusion" est un algorithme de tri qui repose sur le fait que trier deux listes déjà triée est une action rapide.

Il s’agit d’un tri suivant le paradigme "diviser pour régner". Le principe du tri fusion (ou tri par interclassement) est le suivant :
-> On divise en deux moitiés la liste à trier (en prenant par exemple, un élément sur deux pour chacune des listes, ou en faisant moiitié-moitié).
-> On trie chacune d’entre elles.
-> On fusionne les deux moitiés obtenues pour reconstituer la liste triée.

1. Ecrire une fonction récursive fusion qui prend comme paramètres deux listes triées, et qui renvoie la fusion des deux listes. On ne demande pas de vérifier que les deux listes passées en argument sont déjà triées.

def fusion(liste_triee_1, liste_triee_2):
    """
    on fusionne deux listes triées ;
    le principe de cette fonction récursive :
    -> le cas simple c'est si l'une des deux listes est vide ;
    -> sinon on appelle fusion avec une des deux listes réduite de son plus petit élément...
    """



# quelques tests avec deux listes déja triées l1 et l2
l1 = [1,5,9]
l2 = [7,9,12,45]
print(fusion(l1,l2))

2. Ecrire une fonction récursive triFusion qui prend comme paramètre une liste. Le principe est donné ci-dessous.

def triFusion(liste):
    """
    si la liste est vide, on renvoie None
    le cas simple c'est quand la liste contient un seul élément,
    et le cas récursif : on casse en deux et on revoie la fusion du triFusion des deux listes !
    """
    

# un petit test pour vérifier que tout fonctionne bien avec la liste l3
l3 = [4,3,7,9,2,7,427,4,5,45,6,99,88]
print(l3)
print(triFusion(l3))

def fusion(liste_triee_1, liste_triee_2):
    """
    on fusionne deux listes triées ;
    le principe de cette fonction récursive :
    -> les cas simples c'est si les deux sont vides ou si l'une des deux listes est vide ;
    -> sinon on appelle fusion avec une des deux listes réduite de son plus petit élément...
    """
    if not liste_triee_1 :
        return liste_triee_2
    if not liste_triee_2 :
        return liste_triee_1
    if liste_triee_1[0] < liste_triee_2[0]:
        return [liste_triee_1[0]] + fusion(liste_triee_1[1:], liste_triee_2)
    else :
        return [liste_triee_2[0]] + fusion(liste_triee_1, liste_triee_2[1:])

def triFusion(liste):
    """
    si la liste est vide, on renvoie []
    le cas simple c'est quand la liste contient un seul élément,
    sinon on la casse en deux et on revoie la fusion du triFusion des deux listes !
    """
    if len(liste) == 0 :
        return []
    if len(liste) == 1 :
        return liste
    else :
        milieu = len(liste)//2
        liste_gauche = liste[:milieu]
        liste_droite = liste[milieu:]
        return fusion(triFusion(liste_gauche), triFusion(liste_droite))


l3 = [4,3,7,9,2,7,427,4,5,45,6,99,88]
print(l3)
print(triFusion(l3))