Problème — Fusion de $k$ listes triées

on fusionne les listes deux par deux de façon arborescente, exactement comme dans le tri fusion, ce qui est plus efficace que de fusionner les listes une à une.

def fusion(a, b):
    res, 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
    res.extend(a[i:]); res.extend(b[j:])
    return res

def fusion_k_listes(listes):
    if len(listes) == 0:
        return []
    if len(listes) == 1:
        return listes[0]
    m = len(listes) // 2
    gauche = fusion_k_listes(listes[:m])   # diviser
    droite = fusion_k_listes(listes[m:])
    return fusion(gauche, droite)          # combiner

En notant $N$ le nombre total d'éléments, cette approche s'exécute en $O(N\log k)$, contre $O(Nk)$ pour une fusion séquentielle naïve.