Compter les inversions avec le tri fusion

lors de la fusion, lorsqu'un élément de la moitié droite est recopié avant des éléments restants de la moitié gauche, ceux-ci forment autant d'inversions.

def fusion_compte(a, b):
    res, inv = [], 0
    i, j = 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
            inv += len(a) - i      # tous les a[i:] > b[j]
    res.extend(a[i:]); res.extend(b[j:])
    return res, inv

def compte_inversions(tab):
    if len(tab) <= 1:
        return tab, 0
    m = len(tab) // 2
    g, ig = compte_inversions(tab[:m])
    d, idr = compte_inversions(tab[m:])
    f, ifu = fusion_compte(g, d)
    return f, ig + idr + ifu