Écrire fusion triee(a, b) qui fusionne deux tableaux triés en un seul…

def fusion_triee(a, b):
    """Fusionne deux tableaux tries en un seul, en UN parcours.

    Postcondition : le resultat est trie et contient exactement les elements
                    de a et de b (avec leurs repetitions).
    """
    i = j = 0
    resultat = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            resultat.append(a[i]); i += 1
        else:
            resultat.append(b[j]); j += 1
    resultat.extend(a[i:])
    resultat.extend(b[j:])
    assert resultat == sorted(resultat)
    assert len(resultat) == len(a) + len(b)
    return resultat

Les deux extend finaux ne sont pas un détail. La boucle s'arrête dès que l'un des deux tableaux est épuisé ; il reste alors une queue dans l'autre, déjà triée et toute plus grande que ce qui a été posé. L'oublier produit un résultat trop court — et le assert sur la longueur est précisément celui qui le détecterait.

Le coût. Chaque tour place exactement un élément : $n+m$ tours, c'est-à-dire un coût linéaire. sorted(a + b) donnerait le même résultat, mais en jetant l'information dont on disposait — que les deux moitiés étaient déjà triées. C'est cette même idée, exploiter la structure au lieu de la piétiner, qui fait toute la valeur de la dichotomie ; et c'est l'étape centrale du tri fusion, que la terminale étudiera.

Vérification.

assert fusion_triee([1, 3, 5], [2, 4]) == [1, 2, 3, 4, 5]
assert fusion_triee([], [1]) == [1]
assert fusion_triee([1, 1], [1]) == [1, 1, 1]

for _ in range(2000):
    a = sorted(random.randint(0, 20) for _ in range(random.randint(0, 8)))
    b = sorted(random.randint(0, 20) for _ in range(random.randint(0, 8)))
    assert fusion_triee(a, b) == sorted(a + b)

Les tirages contiennent volontairement des doublons et des tableaux vides : ce sont les deux familles de cas où la boucle se comporte différemment.