'''
ATTENTION : on modifie L en place en réalité.
On renvoie le tableau L ici juste pour qu'il s'affiche dans la console en mode interactif !
Sinon, aucune raison de renvoyer L puisque le tableau d'origine est bien modifié.
'''

def tri_insertion(L:list) -> list:
    n = len(L)

    # cas du tableau vide
    if len(L) == 0:
        return L

    # à partir d'ici, on peut dire que la case 0 est la seule triée dans le sous-tableau trié
    for j in range(1, n):  # on va insérer la case d'indice j dans notre sous-tableau trié
        e = L[j]  # on mémorise ce que contient la case qu'on veut insérer
        i = j  # i est l'indice de l'autre case qu'on compare

        # A l'étape j, le sous-tableau L[0,j-1] est trié
        # et on insère L[j] dans ce sous-tableau en déterminant
        # le plus petit i tel que 0 <= i <= j et L[i-1] > L[j].
        while  i > 0 and L[i-1] > e:  # TQ l'indice i vaut au moins 1 et que la case de gauche contient une valeur plus grande que celle qu'on veut insérer
            i = i - 1  # on continue d'aller vers la gauche
        
        # si i != j, on décale le sous tableau L[i,j-1] d’un cran
        # vers la droite et on place L[j] en position i
        if i != j:
            for k in range(j,i,-1):
                L[k] = L[k-1]
            L[i] = e
    return L