def moitie_gauche(L):
    n = len(L)
    return L[:n//2]


def moitie_droite(L):
    n = len(L)
    return L[n//2:]


def fusion(L1, L2):
    L = []
    n1 = len(L1)
    n2 = len(L2)
    i1 = 0
    i2 = 0
    while i1 < n1 or i2 < n2:
        if i1 >= n1:
            L.append(L2[i2])
            i2 = i2 + 1
        elif i2 >= n2:
            L.append(L1[i1])
            i1 = i1 + 1
        else:
            e1 = L1[i1]
            e2 = L2[i2]
            if e1 <= e2:
                L.append(e1)
                i1 = i1 + 1
            else:
                L.append(e2)
                i2 = i2 + 1
    return L


def tri_fusion(L):
    n = len(L)
    if n <= 1:
        return L
    print(L)
    mg = moitie_gauche(L)
    md = moitie_droite(L)
    L1 = tri_fusion(mg)
    L2 = tri_fusion(md)
    return fusion(L1, L2)


# TEST
L = [7, 4, 2, 1, 8, 5, 6, 3]

resultat = tri_fusion(L)

print("Liste triée :", resultat)


tri_fusion([7, 4, 2, 1, 8, 5, 6, 3])