def insere(inf, t, i, v):
    """insère v dans t[0..i[ supposé trié"""
    j = i
    while j > 0 and not inf(t[j - 1], v):
        t[j] = t[j - 1]
        j = j - 1
    t[j] = v

def tri_par_insertion(inf, t):
    """trie le tableau t dans l'ordre croissant
       pour la relation inf"""
    for i in range(1, len(t)):
        insere(inf, t, i, t[i])