Écrire une jointure par tri fusionné

Les deux tables triées se parcourent avec deux indices qui n'avancent jamais en arrière : celui qui pointe la plus petite clé avance, et quand les deux clés s'égalent on produit toutes les combinaisons du bloc commun.

def jointure_tri_fusion(t1, t2, cle):
    """Jointure n:m par tri puis parcours de front.

    Postcondition : mêmes lignes que fusion_multiple, à l'ordre près.
    """
    a = sorted(t1, key=lambda l: l[cle])
    b = sorted(t2, key=lambda l: l[cle])
    i = j = 0
    res = []
    while i < len(a) and j < len(b):
        if a[i][cle] < b[j][cle]:
            i = i + 1
        elif a[i][cle] > b[j][cle]:
            j = j + 1
        else:
            v = a[i][cle]
            i0, j0 = i, j
            while i < len(a) and a[i][cle] == v:
                i = i + 1
            while j < len(b) and b[j][cle] == v:
                j = j + 1
            for x in a[i0:i]:
                for y in b[j0:j]:
                    c = dict(x)
                    c.update(y)
                    res.append(c)
    return res

La terminaison. Le variant est $(\text{len}(a)-i)+(\text{len}(b)-j)$ : entier, positif tant qu'on boucle, et strictement décroissant — chaque branche fait avancer $i$ ou $j$ d'au moins $1$, et la branche d'égalité les fait avancer tous les deux, puisque le bloc commun est non vide. C'est exactement la méthode du chapitre 8.

La validation. $400$ paires de tables tirées au hasard, avec des effectifs de $0$ à $2$ par clé de part et d'autre — donc des clés absentes, uniques et répétées. Les deux fonctions rendent les mêmes lignes, à l'ordre près : $400$ cas passent.

Quand la préférer. L'index coûte de la mémoire — il conserve toute la seconde table ; le tri fusionné n'en demande presque pas, et il donne le résultat déjà trié sur la clé. C'est l'algorithme des bases de données quand les données ne tiennent pas en mémoire, et la raison pour laquelle elles maintiennent des index triés.