Compter les inversions en $O(n\log n)$

Lors de la fusion des listes triées a et b, si b[j] < a[i], cela signifie que b[j] est strictement inférieur à tous les éléments restants de a (qui sont situés à sa gauche dans le tableau global). On ajoute donc le nombre d'éléments restants dans a, soit len(a) - i.

def tri_et_inversions(t: list) -> tuple:
    if len(t) <= 1:
        return (list(t), 0)
    m = len(t) // 2
    a, inv_a = tri_et_inversions(t[:m])
    b, inv_b = tri_et_inversions(t[m:])
    r, i, j, inv = [], 0, 0, inv_a + inv_b
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            r.append(a[i]); i += 1
        else:
            r.append(b[j]); j += 1
            inv += len(a) - i
    return (r + a[i:] + b[j:], inv)