Changement TP/TD sur la fusion récursive

Merci de changer vos notes de TP ainsi que l’exercice 5 du TD2 en cette version :

def fusion(L1:list,L2:list) -> list:
    ''' Entrée : deux listes triées
    Sortie : leur fusion en une liste triée '''
    n, m = len(L1), len(L2)
    if n == 0: return L2
    if m == 0: return L1

    if L1[n-1] >= L2[m-1]:
        R = fusion(L1[0:n-1], L2)
        R.append(L1[n-1])
        return R

    else:
        R = fusion(L1, L2[0:m-1])
        R.append(L2[m-1])
        return R

En effet, dans la précédente je faisais les fusions [L1[0]] + fusion(…, …) pour faire comme des append mais à gauche, mais cette concaténation est en O(n+m) ce qui rendait fusion quadratique et non pas linéaire. Comme append est en O(1), cette version ci-dessus est bien linéaire.

(Pour les optionnaires : j’ai pensé en oCaml, pour lequel les append se font à gauche avec le constructeur de liste :: )

Par ailleurs, j’ai mis un corrigé du TP9 en ligne.