Mesurer le coût de maintenir une liste triée

def mesurer_insertions(n):
    liste = []
    t0 = time.perf_counter()
    for _ in range(n):
        bisect.insort(liste, random.randint(0, 10**6))
    t_tri = time.perf_counter() - t0

    brut = []
    t0 = time.perf_counter()
    for _ in range(n):
        brut.append(random.randint(0, 10**6))
    t_brut = time.perf_counter() - t0
    return t_tri, t_brut

# 20000 insertions : triee 0,034 s, brute 0,0039 s -> rapport 9

Un facteur neuf, et il grandit avec $n$ : le décalage coûte en moyenne $n/2$ déplacements par insertion. Trouver où insérer est gratuit ; insérer ne l'est pas.

La conclusion pratique. Si l'on connaît les données à l'avance, il vaut bien mieux tout ajouter puis trier une seule fois que maintenir le tri au fil de l'eau. La liste triée ne se justifie que si l'on doit interroger entre les insertions — et c'est exactement le raisonnement « trier d'abord, est-ce rentable ? » de la remarque du cours, vu de l'autre côté.