def tri_comptage(L : list) -> list:
    '''Trie par comptage la liste L
    passée en argument '''
    # on détermine le maximum de la liste
    p = L[0]
    for elem in L :
        if elem > p :
            p = elem
    # on compte le nombre d'occurence de chaque entier dans L
    H = [0 for i in range(p + 1)]
    for elem in L :
        H[elem] = H[elem] + 1
    # on construit la liste qui contient les éléments de L triés
    L_trie = []
    for i in range(p+1):
        for j in range(H[i]) :
            L_trie.append(i)
    return L_trie

##

def tri_comptage_piege(L : list) -> list:
    '''Trie par comptage la liste L
    passée en argument '''
    # on détermine le maximum de la liste
    p = L[0]
    for elem in L :
        if elem > p :
            p = elem
    # on compte le nombre d'occurence de chaque entier dans L
    H = [0 for i in range(p + 1)]
    for elem in L :
        H[elem] = H[elem] + 1
    # on construit la liste qui contient les éléments de L triés
    L_trie = []
    for i in range(p+1):
        L_trie = L_trie + [i]*H[i] # ATTENTION A LA COMPLEXITE CACHEE !!
    return L_trie

## comparaison des deux fonctions

from time import perf_counter
from random import randint

n = 100_000
p = 100_000

L = [randint(0, p) for k in range(n)]

start_1 = perf_counter()
tri_comptage(L)
stop_1 = perf_counter()
duree_1 = stop_1 - start_1


start_2 = perf_counter()
tri_comptage_piege(L)
stop_2 = perf_counter()
duree_2 = stop_2 - start_2

print(duree_1, duree_2)