def ou_inserer(l,deb,fin,element): # l est supposée triée dans l'ordre croissant
    while fin > deb:
        mil = (deb+fin)//2
        if l[mil] > element:
            fin = mil
        else:
            deb = mil+1
    if l[deb] > element:
        return deb # indice du premier élément supérieur à element
    return deb+1

def tri_insertion_dicho_en_place(l):
    for i in range(1,len(l)):
        ind = ou_inserer(l,0,i-1,l[i])
        buff = l[i]
        for j in range(i,ind,-1):
            l[j] = l[j-1]
        l[ind] = buff

def tri_insertion_dicho_non_en_place(l):
    liste = [l[0]]
    for i in range(1,len(l)):
        ind = ou_inserer(liste,0,i-1,l[i])
        liste.append(liste[-1]) # tout va bien, promis !
        for j in range(i-1,ind,-1):
            liste[j] = liste[j-1]
        liste[ind] = l[i]
    return liste

def tri_ceratops(dinos):
    ind_deb = 0
    ind_fin = len(dinos)-1
    while ind_deb < ind_fin:
        if dinos[ind_deb][0] == 'c':
            dinos[ind_deb],dinos[ind_fin] = dinos[ind_fin],dinos[ind_deb]
            ind_fin -= 1
        else:
            ind_deb += 1

def tri_ceratops_non_en_place(dinos): # même principe que le tri précédent, ce n'est donc pas un tri dénombrement
    dinosaures = []
    herbivores = 0 # nombre d'herbivores, donc 1 + l'indice du dernier
    for dino in dinos:
        dinosaures.append(dino)
        if dino[0] == 'h':
            if herbivores < len(dinosaures):
                dinosaures[-1],dinosaures[herbivores] = dinosaures[herbivores],dinosaures[-1]
            herbivores += 1
    return dinosaures

def tri_cholomes(champignons): # Une solution de facilité serait de faire deux fois tri_ceratops pour séparer d'abord les mortels des autres (par exemple) puis séparer les toxiques des comestibles
    n = len(champignons)
    nb_comestibles = 0 # l'indice du dernier est donc un de moins
    bn_mortels = n-1 # l'indice du premier mortel sera toujours un de plus que ceci
    for i in range(n):
        while champignons[i][0] == 'm':
            if i <= bn_mortels:
                champignons[i],champignons[bn_mortels] = champignons[bn_mortels],champignons[i]
                bn_mortels -= 1
            else:
                return None # on sait qu'on ne rencontrera plus que des mortels, donc on arrête le tri
        if champignons[i][0] == 'c':
            if i > nb_comestibles:
                champignons[i],champignons[nb_comestibles] = champignons[nb_comestibles],champignons[i]
            nb_comestibles += 1

def split(l,deb,fin): # fin-deb vaudra toujours au moins 2
    if l[deb] > l[fin]:
        l[deb],l[fin] = l[fin],l[deb]
    piv1,piv2 = l[deb],l[fin]
    pos1,pos2 = deb,fin
    for i in range(deb+1,fin):
        if l[i] < piv1:
            l[i],l[pos1],l[pos1+1] = l[pos1+1],l[i],l[pos1] # on force les pivots à être à la bonne place, ce qui complique les choses mais reprend le principe du tri rapide, en plus de restreindre l'appel récursif central dans la fonction principale
            pos1 += 1
        elif l[i] > piv2:
            if i < pos2: # cf. tri_cholomes
                l[i],l[pos2],l[pos2-1] = l[pos2-1],l[i],l[pos2]
                pos2 -= 1
            else:
                return pos1,pos2 # indices des pivots
    return pos1,pos2

def tri_chotomie(l):
    def tri_chotomie_rec(deb,fin): # bornes incluses
        if fin - deb <= 0:
            ()
        elif fin - deb == 1:
            if l[deb] > l[fin]:
                l[deb],l[fin] = l[fin],l[deb]
        else:
            ind1,ind2 = split(l,deb,fin)
            tri_chotomie_rec(deb,ind1-1)
            tri_chotomie_rec(ind1+1,ind2-1)
            tri_chotomie_rec(ind2+1,fin)
    tri_chotomie_rec(0,len(l)-1)

def merge(l1,l2,l3):
    l = []
    n1,n2,n3 = len(l1),len(l2),len(l3)
    i1,i2,i3 = 0,0,0
    while (i1 < n1 and i2 < n2 and i3 < n3):
        if l1[i1] < l2[i2]: # beaucoup de comparaisons sont faites bien trop souvent, mais mémoriser leur résultat est laborieux et tout de même cher
            if l1[i1] < l3[i3]:
                l.append(l1[i1])
                i1 += 1
            else:
                l.append(l3[i3])
                i3 += 1
        elif l2[i2] < l3[i3]:
            l.append(l2[i2])
            i2 += 1
        else:
            l.append(l3[i3])
            i3 += 1
    if i3 == n3:
        while (i1 < n1 and i2 < n2):
            if l1[i1] < l2[i2]:
                l.append(l1[i1])
                i1 += 1
            else:
                l.append(l2[i2])
                i2 += 1
        l.extend(l1[i1:])
        l.extend(l2[i2:])
    elif i2 == n2:
        while (i1 < n1 and i3 < n3):
            if l1[i1] < l3[i3]:
                l.append(l1[i1])
                i1 += 1
            else:
                l.append(l3[i3])
                i3 += 1
        l.extend(l1[i1:])
        l.extend(l3[i3:])
    else:
        while (i2 < n2 and i3 < n3):
            if l2[i2] < l3[i3]:
                l.append(l2[i2])
                i2 += 1
            else:
                l.append(l3[i3])
                i3 += 1
        l.extend(l2[i2:])
        l.extend(l3[i3:])
    return l

def tri_chotomie_fusion(l):
    n = len(l)
    if n < 2:
        return l
    l1,l2,l3 = l[:n//3],l[n//3:2*n//3],l[2*n//3:]
    ll1,ll2,ll3 = tri_chotomie_fusion(l1),tri_chotomie_fusion(l2),tri_chotomie_fusion(l3)
    return merge(ll1,ll2,ll3)

def est_vide(p):
    return p == []

def sommet(p):
    return p[-1]

def tri_piles_en_place(p):
    p_aux = []
    p_mins = []
    while not(est_vide(p) and est_vide(p_aux)):
        p_mins.append(p.pop())
        while not(est_vide(p)):
            if sommet(p) < sommet(p_mins):
                p_aux.append(p_mins.pop())
                p_mins.append(p.pop())
            else:
                p_aux.append(p.pop())
        if not(est_vide(p_aux)): # suivant la parité de la taille de p au début, cette étape sera supprimée à la fin
            p_mins.append(p_aux.pop())
        while not(est_vide(p_aux)):
            if sommet(p_aux) < sommet(p_mins):
                p.append(p_mins.pop())
                p_mins.append(p_aux.pop())
            else:
                p.append(p_aux.pop())
    while not(est_vide(p_mins)):
        p.append(p_mins.pop())

def tri_piles_non_en_place(p):
    p_aux = []
    p_maxs = []
    while not(est_vide(p) and est_vide(p_aux)):
        p_maxs.append(p.pop())
        while not(est_vide(p)):
            if sommet(p) > sommet(p_maxs):
                p_aux.append(p_maxs.pop())
                p_maxs.append(p.pop())
            else:
                p_aux.append(p.pop())
        if not(est_vide(p_aux)):
            p_maxs.append(p_aux.pop())
        while not(est_vide(p_aux)):
            if sommet(p_aux) > sommet(p_maxs):
                p.append(p_maxs.pop())
                p_maxs.append(p_aux.pop())
            else:
                p.append(p_aux.pop())
    return p_maxs