Le tri de Shell applique le tri par insertion à des éléments distants…

def tri_shell(t):
    """Tri par insertion à pas décroissant."""
    n = len(t)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            x = t[i]
            j = i
            while j >= gap and t[j - gap] > x:
                t[j] = t[j - gap]
                j = j - gap
            t[j] = x
        gap = gap // 2

Validation : $2000$ tableaux tirés au hasard — $2000$ cas passent. Remarquez que la dernière étape, $g=1$, est exactement le tri par insertion du cours : la correction est donc acquise quoi que fassent les étapes précédentes. Elles ne servent qu'à réduire le désordre.

La mesure, sur des tableaux aléatoires.

Les rapports de Shell tournent autour de $2,4$ — nettement sous le $4$ du quadratique, sans être le $2$ franc d'un coût linéaire. Ceux de l'insertion oscillent autour de $4$, comme attendu.

Pourquoi cela marche. Le résultat de l'exercice de TD sur les inversions donne l'explication complète : le coût du tri par insertion est proportionnel au nombre d'inversions. Les passages à grand pas déplacent les éléments de loin, donc suppriment beaucoup d'inversions d'un coup ; quand arrive le passage $g=1$, il ne reste presque rien à faire.

Une honnêteté nécessaire. Le coût exact du tri de Shell dépend de la suite de pas choisie, et pour la suite « diviser par deux » employée ici, il n'est pas connu sous forme close — c'est un problème ouvert. Les rapports mesurés décrivent nos quatre tailles ; ils ne démontrent pas de loi. Dire « environ $2,4$, sur cette plage » est tout ce qu'on peut affirmer.