Diviser pour régner et tri fusion : fiche de Terminale NSI
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
Diviser pour régner : on découpe le problème en sous-problèmes, on les résout, puis on combine les résultats 2.
Le tri fusion coupe le tableau en deux moitiés, trie chacune récursivement, puis fusionne deux tableaux déjà triés.
La fusion parcourt les deux tableaux une seule fois : on compare les deux premiers éléments restants et on prend le plus petit.
Le cas de base est un tableau de 0 ou 1 élément : il est déjà trié. Sans lui, la récursion ne s'arrête pas.
Le découpage en moitiés donne environ log2n niveaux, chacun coûtant de l'ordre de n opérations : le coût est bien meilleur que celui d'un tri quadratique.
Le principe : trois phases
DiviserCouper le problème en sous-problèmes plus petits
RégnerRésoudre chaque sous-problème, souvent récursivement
CombinerAssembler les solutions partielles
Les trois phases de diviser pour régner · Dans le tri fusion : couper, trier chaque moitié, fusionner.
Le tri fusion étape par étape
La fusion : le cœur de l'algorithme
def fusion(g, d):
res, i, j = [], 0, 0
while i < len(g) and j < len(d):
if g[i] <= d[j]:
res.append(g[i]); i += 1
else:
res.append(d[j]); j += 1
return res + g[i:] + d[j:]
def tri_fusion(t):
if len(t) <= 1:
return t
m = len(t) // 2
return fusion(tri_fusion(t[:m]), tri_fusion(t[m:]))
Coût et intérêt
Questions flash
4 questions · correction immédiate · ton score reste sur ton appareil.
On découpe d'abord (diviser), on résout les sous-problèmes (régner), puis on assemble les résultats (combiner). Inverser « diviser » et « régner » est tentant à cause du nom de la méthode, mais on ne peut pas résoudre des sous-problèmes avant de les avoir créés.
Un tableau de 0 ou 1 élément est déjà trié : le renvoyer arrête les appels récursifs. Sans cela, on découperait indéfiniment. La fusion, elle, exige au contraire des tableaux déjà triés, et le tri fusion présenté ne trie pas en place.
On prend successivement 1, 2, 3, 4, 6 puis le reste 9. L'erreur tentante serait de simplement concaténer les deux tableaux, ce qui donnerait [1,4,6,2,3,9], non trié.
À chaque niveau la taille est divisée par 2 : 16→8→4→2→1, soit 4 niveaux, car log216=4. Répondre 16 ou 8 confond le nombre de niveaux avec la taille du tableau.
Les questions qu'on se pose
Quelle différence entre « diviser pour régner » et une simple récursion ?
Toute récursion se ramène à des problèmes plus petits, mais « diviser pour régner » impose en plus de découper en sous-problèmes de même nature puis de combiner leurs solutions 2. Une fonction factorielle est récursive sans vraiment combiner plusieurs sous-résultats indépendants.
Que peut-on te demander au bac sur le tri fusion ?
On peut te demander de compléter ou d'écrire la fonction de fusion, de dérouler l'algorithme sur un petit tableau, d'expliquer pourquoi la récursion termine, et de justifier que le coût est meilleur que celui d'un tri quadratique. Entraîne-toi surtout à dérouler la fusion à la main.
Le tri fusion est-il toujours le meilleur choix ?
Non. Il est régulier et rapide sur de grands tableaux, mais la version vue ici demande de la mémoire supplémentaire. Pour un petit tableau, un tri simple suffit souvent.