Numérique et sciences informatiques (spécialité) · TerminaleBac

Diviser pour régner et tri fusion : cours 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 plus petits, on les résout (souvent par récursivité), puis on combine les résultats ¹.
Trois phases : diviser, régner, combiner ².
Tri fusion : on coupe le tableau en deux moitiés, on trie chaque moitié récursivement, puis on fusionne deux listes triées en un seul parcours.
Cas de base obligatoire : un tableau de 0 ou 1 élément est déjà trié, sinon la récursivité ne s'arrête jamais.
Coût du tri fusion : environ $\log_2 n$ niveaux, chacun coûtant de l'ordre de $n$ opérations, donc de l'ordre de $n\log_2 n$ , contre $n^2$ pour les tris simples.

Pourquoi découper un problème ?

Tu connais déjà plusieurs tris : le tri par sélection et le tri par insertion. Ils fonctionnent, mais lorsque le tableau double de taille, le temps de calcul est à peu près multiplié par quatre. On parle de temps quadratique, et c'est précisément le défaut que la méthode de ce chapitre permet de corriger ¹.

L'idée est ancienne et très naturelle : devant un problème trop gros, on le coupe en morceaux plus petits, plus faciles à traiter, puis on recolle les réponses. Imagine que tu doives trier un paquet de mille copies par ordre alphabétique. Tu peux les trier une à une dans un seul tas, ou bien former dix paquets de cent copies, faire trier chaque paquet par des camarades, puis rassembler les paquets déjà triés. La seconde méthode est celle de l'algorithmique « diviser pour régner ».

Dans ce cours, tu vas :

définir précisément la méthode et ses trois phases ;
voir où elle apparaît en dehors des tris ;
construire pas à pas le tri fusion en Python ;
justifier son efficacité par un raisonnement sur le nombre d'opérations ;
éviter les erreurs que l'on retrouve le plus souvent dans les copies de bac.

Tu as besoin de la récursivité et d'une bonne aisance avec les listes Python. Les arbres binaires vus avant ce chapitre te serviront d'image mentale : les appels récursifs du tri fusion forment justement un arbre.

La méthode en trois phases

DiviserCouper en sous-problèmes plus petits
RégnerRésoudre chaque sous-problème, souvent par récursivité
CombinerAssembler les solutions partielles

Les trois phases de diviser pour régner · Les trois phases de la méthode.

Où rencontre-t-on cette méthode ?

Le tri n'est pas le seul domaine concerné. Plusieurs algorithmes classiques suivent le même schéma ² :

la rotation d'une image d'un quart de tour : on découpe l'image en carreaux de plus en plus petits, jusqu'à des carreaux d'un seul pixel ² ;
la recherche des deux points les plus rapprochés dans un ensemble de points ² ;
l'algorithme d'Euclide, qui fournit le PGCD de deux entiers : à chaque étape, on remplace les deux valeurs par des valeurs plus petites, ce qui revient à poser la même question sur des données réduites ².

La ressource Éduscol consacrée à ce sujet présente trois exemples d'algorithmes de ce type, dont le tri fusion, et rappelle que la méthode permet d'éviter le temps quadratique obtenu avec des méthodes directes sur un tableau de nombres ¹.

Quelques algorithmes de type diviser pour régner
Algorithme	Problème traité	Découpage
Tri fusion	Trier un tableau	Deux moitiés du tableau
Rotation d'image	Tourner une image d'un quart de tour	Carreaux de plus en plus petits, jusqu'au pixel
Points les plus rapprochés	Trouver les deux points les plus proches	Sous-ensembles de points
Algorithme d'Euclide	Calculer un PGCD	Nombres plus petits à chaque étape

Quelques algorithmes de type diviser pour régner · D'après les exemples cités dans le dossier de sources.

Le tri fusion : principe

Le tri fusion applique la méthode au problème « trier un tableau de nombres ». Voici comment les trois phases se traduisent.

Diviser : on coupe le tableau en deux moitiés de tailles égales, à un élément près.
Régner : on trie chacune des deux moitiés en appelant la même fonction. Un tableau vide ou d'un seul élément est déjà trié : c'est le cas de base.
Combiner : on fusionne les deux moitiés triées en un unique tableau trié.

ExempleFusion de [2, 5, 9] et [3, 4, 12]

Élément comparé (gauche / droite)	Plus petit	Résultat
2 / 3	2	[2]
5 / 3	3	[2, 3]
5 / 4	4	[2, 3, 4]
5 / 12	5	[2, 3, 4, 5]
9 / 12	9	[2, 3, 4, 5, 9]

La liste de gauche est épuisée ; on recopie le reste de la droite : [12]. Résultat : [2, 3, 4, 5, 9, 12]. Chaque élément n'a été examiné qu'une fois : c'est ce qui rend la fusion rapide.

Tri fusion

Diviser
- Deux moitiés
- Milieu = n // 2
Régner
- Appels récursifs
- Cas de base : 0 ou 1
Combiner
- Fusion de listes
- Un seul parcours
- Stable avec <=
Coût
- log n niveaux
- n par niveau
- n log n au total

Le tri fusion en un coup d'œil · Les idées clés du tri fusion.

Le tri fusion en Python

MéthodeÉcrire la fonction de fusion

On écrit d'abord la phase « combiner », seule, et on la teste.

def fusion(a, b):
    """Fusionne deux listes triées a et b."""
    i, j = 0, 0
    resultat = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            resultat.append(a[i])
            i += 1
        else:
            resultat.append(b[j])
            j += 1
    resultat.extend(a[i:])
    resultat.extend(b[j:])
    return resultat

La boucle while s'arrête dès qu'une des deux listes est épuisée. Les deux dernières lignes recopient ce qui reste : l'une des deux tranches est vide, l'autre contient la fin de la liste non épuisée, déjà triée et dont tous les éléments sont supérieurs ou égaux à ceux déjà placés.

MéthodeÉcrire la fonction récursive

def tri_fusion(t):
    """Renvoie une nouvelle liste triée contenant les éléments de t."""
    if len(t) <= 1:
        return t
    milieu = len(t) // 2
    gauche = tri_fusion(t[:milieu])
    droite = tri_fusion(t[milieu:])
    return fusion(gauche, droite)

Les trois phases se lisent directement :

diviser : le calcul de milieu et les deux tranches t[:milieu] et t[milieu:] ;
régner : les deux appels récursifs, et le return t du cas de base ;
combiner : l'appel à fusion.

Pourquoi le tri fusion est efficace

Compter précisément chaque instruction serait fastidieux. On compte plutôt le nombre d'opérations élémentaires dominantes, ici les comparaisons et les copies d'éléments. Pour une fusion de deux listes de tailles totales $n$ , chaque tour de boucle place un élément dans le résultat et en examine un autre au plus une fois : le coût est donc proportionnel à $n$ .

Démonstration · Coût du tri fusion pour $n = 2^k$

Notons $T(n)$ le coût pour un tableau de taille $n$ , que l'on prend égale à une puissance de 2 pour simplifier : $n=2^k$ . On modélise la fusion par un coût de $n$ opérations et le cas de base par un coût nul : $T(1)=0$ .

Pour $n\ge 2$ , on trie deux moitiés de taille $n/2$ , puis on fusionne :

$T(n)=2\,T\!\left(\frac n2\right)+n.$

Divisons par $n$ et posons $u_k=\dfrac{T(2^k)}{2^k}$ . On obtient

$u_k=\frac{2\,T(2^{k-1})+2^k}{2^k}=\frac{T(2^{k-1})}{2^{k-1}}+1=u_{k-1}+1,\qquad u_0=0.$

La suite $(u_k)$ est arithmétique de raison 1 : $u_k=k$ . Donc

$T(n)=n\,k=n\log_2 n.$

Vérification : $T(2)=2$ , $T(4)=2\times 2+4=8=4\times 2$ , $T(8)=2\times 8+8=24=8\times 3$ .

On peut aussi lire ce résultat sur l'arbre des appels. Il y a $\log_2 n$ niveaux de fusions ; à chaque niveau, les fusions portent au total sur les $n$ éléments, donc coûtent $n$ au total. Le produit donne $n\log_2 n$ .

On dit que la complexité du tri fusion est en $O(n\log n)$ , alors que celle des tris par sélection et par insertion est en $O(n^2)$ dans le pire cas.

Variantes, pièges et méthode d'examen

MéthodeVersion avec indices, sans copie de tranches

On peut éviter de créer des listes à chaque appel en travaillant sur les indices debut (inclus) et fin (exclu) d'un même tableau, et en utilisant un tableau auxiliaire pour la fusion.

def tri_fusion_indices(t, debut, fin):
    if fin - debut <= 1:
        return
    milieu = (debut + fin) // 2
    tri_fusion_indices(t, debut, milieu)
    tri_fusion_indices(t, milieu, fin)
    gauche = t[debut:milieu]
    droite = t[milieu:fin]
    i = j = 0
    for k in range(debut, fin):
        if j >= len(droite) or (i < len(gauche) and gauche[i] <= droite[j]):
            t[k] = gauche[i]
            i += 1
        else:
            t[k] = droite[j]
            j += 1

Cette version modifie le tableau passé en paramètre et ne renvoie rien. Elle est plus délicate à écrire : le piège principal est de bien traiter le cas où l'une des deux listes est épuisée, ce que fait la condition j >= len(droite).

Exercices corrigés

Exercice 1 Fusionner deux listes triées à la main

★☆☆Environ 8 min

On considère les listes triées $a=[3,27,38,43]$ et $b=[5,9,10,82]$ .

Applique l'algorithme de fusion et écris la liste obtenue.
Combien de comparaisons entre un élément de $a$ et un élément de $b$ as-tu effectuées ?

Indice 1

Garde deux indices et compare à chaque fois les éléments courants.

Indice 2

Quand une liste est épuisée, on ne compare plus : on recopie le reste.

Voir la correction pas à pas

On compare 3 et 5 : 3 passe. Comparaison n°1, résultat [3].
On compare 27 et 5 : 5 passe. Comparaison n°2, résultat [3, 5].
On compare 27 et 9 : 9 passe. Comparaison n°3.
On compare 27 et 10 : 10 passe. Comparaison n°4, résultat [3, 5, 9, 10].
On compare 27 et 82 : 27 passe. Comparaison n°5.
On compare 38 et 82 : 38 passe. Comparaison n°6.
On compare 43 et 82 : 43 passe. Comparaison n°7. La liste $a$ est épuisée.
On recopie le reste de $b$ : [82]. Résultat : [3, 5, 9, 10, 27, 38, 43, 82], obtenu en 7 comparaisons.

Chaque comparaison place un élément dans le résultat, sauf pour les éléments recopiés à la fin. Ici, 8 éléments au total et 1 recopié sans comparaison : 7 comparaisons. Dans le pire cas, une fusion de $n$ éléments demande $n-1$ comparaisons.

Exercice 2 Calculer un coût avec la relation de récurrence

★★☆Environ 10 min

On modélise le coût du tri fusion par $T(1)=0$ et $T(n)=2\,T(n/2)+n$ pour $n=2^k$ , $k\ge 1$ .

Calcule $T(2)$ , $T(4)$ , $T(8)$ puis $T(16)$ .
Vérifie que ces valeurs coïncident avec $n\log_2 n$ .

Indice 1

Utilise chaque valeur pour calculer la suivante.

Indice 2

Pour $n=16$ , $\log_2 16=4$ .

Voir la correction pas à pas

$T(2)=2\,T(1)+2=0+2=2$ .
$T(4)=2\,T(2)+4=4+4=8$ .
$T(8)=2\,T(4)+8=16+8=24$ .
$T(16)=2\,T(8)+16=48+16=64$ .
Comparaison avec $n\log_2 n$ : $2\times1=2$ , $4\times2=8$ , $8\times3=24$ , $16\times4=64$ . Les valeurs coïncident.

Le coût est bien $n\log_2 n$ : $T(16)=64$ . Pour un tri quadratique, on aurait de l'ordre de $16^2=256$ opérations ; l'écart se creuse vite quand $n$ grandit.

Exercice 3 Comparer un tri quadratique et le tri fusion

★★★Environ 12 min

Pour trier $n=1024$ éléments, on estime le coût d'un tri quadratique à $n^2$ opérations et celui du tri fusion à $n\log_2 n$ opérations.

Calcule chacun de ces deux coûts.
Calcule le rapport entre le coût quadratique et le coût du tri fusion.
Explique en une phrase pourquoi ce rapport augmente avec $n$ .

Indice 1

$1024=2^{10}$ , donc $\log_2 1024=10$ .

Indice 2

Le rapport se simplifie : $\dfrac{n^2}{n\log_2 n}=\dfrac{n}{\log_2 n}$ .

Voir la correction pas à pas

Coût quadratique : $1024^2=1\,048\,576$ .
Coût du tri fusion : $1024\times10=10\,240$ .
Rapport : $\dfrac{1\,048\,576}{10\,240}=102{,}4$ .
Explication : le rapport vaut $\dfrac{n}{\log_2 n}$ ; le numérateur croît bien plus vite que le logarithme, donc l'avantage du tri fusion grandit avec la taille du tableau.

Pour 1024 éléments, le tri fusion fait environ 100 fois moins d'opérations que le tri quadratique. Il s'agit d'un ordre de grandeur de modèles de coût, pas d'un chronométrage réel, qui dépend aussi de la machine et du langage.

Les questions qu'on se pose

Quelle différence y a-t-il entre diviser pour régner et la récursivité ?

La récursivité est une façon d'écrire une fonction qui s'appelle elle-même. Diviser pour régner est une stratégie de résolution en trois phases (diviser, régner, combiner) ², qui s'écrit souvent de manière récursive. Une fonction récursive n'est pas forcément de type diviser pour régner : une factorielle réduit le problème de 1 à chaque appel au lieu de le couper en parties de taille comparable.

Pourquoi le tri fusion est-il plus rapide que le tri par insertion ?

Le tri par insertion peut déplacer chaque élément sur une distance proportionnelle à $n$ , d'où un coût en $n^2$ dans le pire cas. Le tri fusion ne compare jamais deux éléments inutilement : chaque niveau de fusion traite chaque élément une seule fois, et il y a seulement environ $\log_2 n$ niveaux. Le coût total est de l'ordre de $n\log_2 n$ .

Le tri fusion est-il toujours le meilleur choix ?

Non. Il demande de la mémoire supplémentaire pour les listes intermédiaires, et sur de très petits tableaux le coût des appels récursifs peut dépasser le gain. En revanche, son coût en $n\log n$ ne dépend pas de l'ordre initial des données, ce qui est un avantage quand on veut une performance prévisible.

Que faut-il savoir pour le bac sur ce chapitre ?

Il faut savoir expliquer les trois phases, écrire ou compléter une fonction de fusion et la fonction récursive du tri fusion, dérouler l'algorithme sur un petit tableau, justifier la terminaison et la correction, et expliquer qualitativement pourquoi la complexité est meilleure que quadratique. Les théorèmes généraux de calcul de complexité, comme le Master theorem ², ne sont pas à connaître.

Comment vérifier mon tri fusion avant de le rendre ?

Teste d'abord fusion seule avec des listes de tailles différentes, dont une liste vide. Puis teste tri_fusion sur un tableau vide, un tableau d'un élément, un tableau déjà trié, un tableau trié à l'envers et un tableau avec des doublons. Compare enfin le résultat avec celui de la fonction sorted de Python sur des tableaux aléatoires.

Sources

Algorithmes diviser pour régner et tri fusion - Ressource Éduscol, Éduscol. Consulté le 7 novembre 2026.
Diviser pour régner (informatique), Wikipédia. Consulté le 7 novembre 2026.

Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.

Signaler une erreur sur cette page

Diviser pour régner et tri fusion : cours de Terminale NSI

L'essentiel

Pourquoi découper un problème ?

La méthode en trois phases

Où rencontre-t-on cette méthode ?

Le tri fusion : principe

Le tri fusion en Python

Pourquoi le tri fusion est efficace

Variantes, pièges et méthode d'examen

Exercices corrigés

Exercice 1 Fusionner deux listes triées à la main

Exercice 2 Calculer un coût avec la relation de récurrence

Exercice 3 Comparer un tri quadratique et le tri fusion

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur