Compter les comparaisons que fait réellement le sorted de Python, sur…

Le procédé. On ne peut pas instrumenter sorted ; on instrumente donc les objets qu'on lui donne, en comptant les appels à leur comparaison.

class Espion:
    compteur = 0
    def __init__(self, v):
        self.v = v
    def __lt__(self, autre):
        Espion.compteur = Espion.compteur + 1
        return self.v < autre.v

def comparaisons_sorted(valeurs):
    Espion.compteur = 0
    sorted([Espion(v) for v in valeurs])
    return Espion.compteur

**Ce qui surprend : $n-1$ comparaisons sur un tableau *inversé***, exactement comme sur un tableau trié. Le tri par insertion y ferait $n(n-1)/2$, soit $1279200$ pour $n=1600$ — huit cents fois plus.

L'explication. L'algorithme de Python, Timsort, commence par repérer les suites monotones déjà présentes. Une suite décroissante est détectée en $n-1$ comparaisons et simplement retournée — opération qui ne compare rien. Le tableau devient trié, et il n'y a plus rien à faire. Un tableau parfaitement inversé est donc, pour Timsort, un cas aussi facile qu'un tableau trié.

Sur les tableaux aléatoires, les rapports valent $2,38$, $2,29$, $2,28$, $2,24$ : la même signature en $n{\log }_{2}n$ que le tri fusion — et pour cause, Timsort est une fusion, sur des morceaux déjà ordonnés.

La morale. Une bibliothèque n'est pas une boîte noire dont on devine le coût : on peut le mesurer, et il réserve des surprises. Le pire cas d'un algorithme n'est pas le pire cas d'un autre.