Tri fusion (merge sort)

Le tri fusion utilise la stratégie diviser pour regner. L'idee est brillante : si tu ne sais pas trier une grande liste, coupe-la en deux, trie chaque moitie séparément, puis fusionne les deux moities triees.

C'est comme trier un paquet de copies : tu divises le paquet en deux, tu demandes a deux collegues de trier chaque moitie, puis tu fusionnes les deux paquets tries en comparant les copies du dessus.

La fusion de deux listes triees est simple : tu compares les premiers éléments de chaque liste, tu prends le plus petit, et tu avances dans cette liste.

Le tri fusion est toujours O(n log n), meme dans le pire cas. C'est beaucoup plus rapide que O(n²) pour les grandes listes.

Écris une fonction tri_fusion(lst) qui retourne une nouvelle liste triee (sans modifier l'originale), et une fonction fusionner(gauche, droite) qui fusionne deux listes deja triees.

Exemple :
tri_fusion([38, 27, 43, 3, 9]) renvoie [3, 9, 27, 38, 43]

Tests (3/4)

Tri basique

assert tri_fusion([38, 27, 43, 3, 9]) == [3, 9, 27, 38, 43]

Liste vide

assert tri_fusion([]) == []

Un élément

assert tri_fusion([7]) == [7]

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

def tri_fusion(lst):
    if len(lst) <= 1:
        return lst
    milieu = len(lst) // 2
    gauche = tri_fusion(lst[:milieu])
    droite = tri_fusion(lst[milieu:])
    return fusionner(gauche, droite)

def fusionner(gauche, droite):
    résultat = []
    i = j = 0
    while i < len(gauche) and j < len(droite):
        if gauche[i] <= droite[j]:
            résultat.append(gauche[i])
            i += 1
        else:
            résultat.append(droite[j])
            j += 1
    résultat.extend(gauche[i:])
    résultat.extend(droite[j:])
    return résultat

← Tri par insertion Tri rapide (quick sort) →

solution.py

Bravo!

Tri fusion (merge sort)

Tests (3/4)

Indices (3 disponibles)

Solution officielle