Fusionner deux listes triées

Le code.

def fusion(A, B):
    # A et B sont TRIEES par ordre croissant
    i, j = 0, 0
    R = []
    while i < len(A) and j < len(B):
        if A[i] <= B[j]:
            R.append(A[i])
            i = i + 1
        else:
            R.append(B[j])
            j = j + 1
    # l'une des deux listes est epuisee : on recopie l'autre
    while i < len(A):
        R.append(A[i])
        i = i + 1
    while j < len(B):
        R.append(B[j])
        j = j + 1
    return R

print(fusion([1, 4, 7], [2, 3, 9, 11]))    # [1, 2, 3, 4, 7, 9, 11]

Pourquoi le résultat est trié. À chaque tour, on ajoute le plus petit des deux éléments encore disponibles. Comme $A$ et $B$ sont triées, cet élément est le plus petit de tous ceux qui restent : il est donc supérieur ou égal à tous ceux déjà placés. La liste R reste ainsi croissante à chaque ajout.

Terminaison. À chaque tour de chacune des trois boucles, i + j augmente strictement d'une unité ; comme cette quantité est majorée par len(A) + len(B), les boucles s'arrêtent.

Les deux boucles de recopie sont indispensables. La première boucle s'arrête dès que l'une des listes est épuisée ; les éléments restants de l'autre n'ont pas encore été placés. Les oublier produit une liste trop courte, sans aucun message d'erreur — le défaut est invisible sur des exemples où la dernière valeur vient de la liste qui s'épuise en dernier.

Le coût. Chaque comparaison A[i] <= B[j] fait avancer i ou j d'un cran, et le total des avancées vaut $n+m$ où $n$ et $m$ sont les longueurs. Il y a donc au plus $n+m-1$ comparaisons, soit un coût proportionnel à $n+m$. Concaténer puis trier coûterait davantage : un tri général demande de l'ordre de $(n+m)\log (n+m)$ comparaisons, et surtout il n'utiliserait pas l'information — précieuse — que les deux listes sont déjà triées.