Définition — Tri par fusion Le tri par fusion est un algorithme de tri basé sur le paradigme Diviser pour régner (Divide and Conquer). Il divise récursivement le tableau en deux moitiés, trie chacune, puis les fusionne pour produire un tableau trié.

C'est l'un des algorithmes de tri les plus efficaces et les plus populaires, avec une complexité temporelle garantie de Θ(n log n) dans tous les cas.

Stratégie — Diviser pour régner

Les trois étapes Pour trier le sous-tableau T[debut..fin] avec milieu = (debut + fin) / 2:

Diviser — Couper T[debut..fin] en deux moitiés : T[debut..milieu] et T[milieu+1..fin].
Régner — Trier récursivement chaque moitié. Cas de base : un tableau d'un seul élément est déjà trié.
Combiner — Fusionner les deux moitiés triées en un seul tableau trié.

Exemple de division — tableau [38, 27, 43, 3, 9, 82, 10]

Arbre de récursion — phase de division

[38, 27, 43, 3, 9, 82, 10]
         ↙                ↘
[38, 27, 43, 3]      [9, 82, 10]
    ↙       ↘          ↙      ↘
[38, 27]  [43, 3]    [9, 82]  [10]
  ↙  ↘     ↙   ↘     ↙   ↘
[38] [27] [43]  [3]  [9] [82]

Phase fusion (remontée) :
[27,38]  [3,43]     [9,82]  [10]
    ↘       ↙           ↘   ↙
  [3,27,38,43]        [9,10,82]
         ↘               ↙
       [3, 9, 10, 27, 38, 43, 82]

Algorithme

Pseudocode

fonction triFusion(T, debut, fin) :
    Si debut >= fin alors
        retourner          ← cas de base : sous-tableau de taille 1

    milieu ← (debut + fin) // 2

    triFusion(T, debut, milieu)       ← trier la moitié gauche
    triFusion(T, milieu + 1, fin)     ← trier la moitié droite

    fusion(T, debut, milieu, fin)     ← combiner les deux moitiés triées

Cas de base et condition d'arrêt La récursion s'arrête quand debut >= fin (sous-tableau d'un seul élément ou vide). Un tableau d'un élément est trivialement trié — c'est le cas de base.

Fonction fusion — le cœur de l'algorithme

La fusion est l'étape clé : elle prend deux sous-tableaux triés T[debut..milieu] et T[milieu+1..fin] et les combine en un seul tableau trié en place.

Pseudocode — fusion

fonction fusion(T, debut, milieu, fin) :
    Copier T[debut..milieu] dans G[]
    Copier T[milieu+1..fin] dans D[]

    i ← 0, j ← 0, k ← debut

    Tant que i < |G| ET j < |D| :
        Si G[i] ≤ D[j] alors
            T[k] ← G[i];  i ← i + 1
        Sinon
            T[k] ← D[j];  j ← j + 1
        k ← k + 1

    Copier les éléments restants de G dans T (si i < |G|)
    Copier les éléments restants de D dans T (si j < |D|)

Trace de fusion — G = [3, 27, 38, 43] et D = [9, 10, 82]

Étape	G[i]	D[j]	Choix	T résultat partiel
1	3	9	G[i]=3 ≤ D[j]=9 → G	[3, ...]
2	27	9	D[j]=9 < G[i]=27 → D	[3, 9, ...]
3	27	10	D[j]=10 < G[i]=27 → D	[3, 9, 10, ...]
4	27	82	G[i]=27 ≤ D[j]=82 → G	[3, 9, 10, 27, ...]
5	38	82	G[i]=38 → G	[3, 9, 10, 27, 38, ...]
6	43	82	G[i]=43 → G	[3, 9, 10, 27, 38, 43, ...]
7	—	82	G épuisé → copier D restant	[3, 9, 10, 27, 38, 43, 82]

Implémentations

def fusion(tab, debut, milieu, fin):
    """Fusionne deux sous-tableaux triés tab[debut..milieu] et tab[milieu+1..fin]."""
    G = tab[debut : milieu + 1]   # copie de la moitié gauche
    D = tab[milieu + 1 : fin + 1] # copie de la moitié droite

    i = j = 0
    k = debut

    # Comparer et placer le plus petit élément
    while i < len(G) and j < len(D):
        if G[i] <= D[j]:
            tab[k] = G[i]; i += 1
        else:
            tab[k] = D[j]; j += 1
        k += 1

    # Copier les éléments restants
    while i < len(G):
        tab[k] = G[i]; i += 1; k += 1
    while j < len(D):
        tab[k] = D[j]; j += 1; k += 1


def triFusion(tab, debut=0, fin=None):
    """Trie tab[debut..fin] par fusion (en place)."""
    if fin is None:
        fin = len(tab) - 1
    if debut < fin:
        milieu = (debut + fin) // 2
        triFusion(tab, debut, milieu)       # trier moitié gauche
        triFusion(tab, milieu + 1, fin)     # trier moitié droite
        fusion(tab, debut, milieu, fin)     # fusionner


# Test
A = [64, 25, 12, 22, 11]
print("Avant :", A)
triFusion(A)
print("Après :", A)

#include <stdio.h>
#include <stdlib.h>

void fusion(int tab[], int debut, int milieu, int fin) {
    int n1 = milieu - debut + 1;
    int n2 = fin - milieu;

    /* Tableaux temporaires */
    int *G = malloc(n1 * sizeof(int));
    int *D = malloc(n2 * sizeof(int));

    for (int i = 0; i < n1; i++) G[i] = tab[debut + i];
    for (int j = 0; j < n2; j++) D[j] = tab[milieu + 1 + j];

    int i = 0, j = 0, k = debut;

    while (i < n1 && j < n2) {
        if (G[i] <= D[j]) tab[k++] = G[i++];
        else               tab[k++] = D[j++];
    }
    while (i < n1) tab[k++] = G[i++];
    while (j < n2) tab[k++] = D[j++];

    free(G); free(D);
}

void triFusion(int tab[], int debut, int fin) {
    if (debut < fin) {
        int milieu = (debut + fin) / 2;
        triFusion(tab, debut, milieu);
        triFusion(tab, milieu + 1, fin);
        fusion(tab, debut, milieu, fin);
    }
}

void afficher(int tab[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", tab[i]);
    printf("\n");
}

int main() {
    int tab[] = {64, 25, 12, 22, 11};
    int n = 5;
    printf("Avant : "); afficher(tab, n);
    triFusion(tab, 0, n - 1);
    printf("Après : "); afficher(tab, n);
    return 0;
}

import java.util.Arrays;

public class TriFusion {

    static void fusion(int[] tab, int debut, int milieu, int fin) {
        int n1 = milieu - debut + 1;
        int n2 = fin - milieu;

        int[] G = new int[n1];
        int[] D = new int[n2];

        for (int i = 0; i < n1; i++) G[i] = tab[debut + i];
        for (int j = 0; j < n2; j++) D[j] = tab[milieu + 1 + j];

        int i = 0, j = 0, k = debut;

        while (i < n1 && j < n2) {
            if (G[i] <= D[j]) tab[k++] = G[i++];
            else               tab[k++] = D[j++];
        }
        while (i < n1) tab[k++] = G[i++];
        while (j < n2) tab[k++] = D[j++];
    }

    static void triFusion(int[] tab, int debut, int fin) {
        if (debut < fin) {
            int milieu = (debut + fin) / 2;
            triFusion(tab, debut, milieu);
            triFusion(tab, milieu + 1, fin);
            fusion(tab, debut, milieu, fin);
        }
    }

    public static void main(String[] args) {
        int[] tab = {64, 25, 12, 22, 11};
        System.out.println("Avant : " + Arrays.toString(tab));
        triFusion(tab, 0, tab.length - 1);
        System.out.println("Après : " + Arrays.toString(tab));
    }
}

def tri_fusion(lst):
    """
    Version fonctionnelle (non en place) : retourne une nouvelle liste triée.
    Plus lisible, mais utilise plus de mémoire (O(n) supplémentaire).
    """
    if len(lst) <= 1:
        return lst

    milieu = len(lst) // 2
    G = tri_fusion(lst[:milieu])
    D = tri_fusion(lst[milieu:])
    return fusionner(G, D)


def fusionner(G, D):
    """Fusionne deux listes triées en une seule liste triée."""
    resultat = []
    i = j = 0
    while i < len(G) and j < len(D):
        if G[i] <= D[j]:
            resultat.append(G[i]); i += 1
        else:
            resultat.append(D[j]); j += 1
    return resultat + G[i:] + D[j:]   # concaténer les restes


# Test avec comptage des comparaisons
comparaisons = 0

def fusionner_compter(G, D):
    global comparaisons
    resultat = []
    i = j = 0
    while i < len(G) and j < len(D):
        comparaisons += 1
        if G[i] <= D[j]:
            resultat.append(G[i]); i += 1
        else:
            resultat.append(D[j]); j += 1
    return resultat + G[i:] + D[j:]


import random
n = 100
lst = random.sample(range(1000), n)
trie = tri_fusion(lst)
print(f"n = {n} → {comparaisons} comparaisons (≈ n·log₂n = {n * 7:.0f})")
print(f"Trié correctement : {trie == sorted(lst)}")

Sortie

Avant : [64, 25, 12, 22, 11]
Après : [11, 12, 22, 25, 64]

Analyse de la complexité

Théorème — Complexité du tri par fusion La relation de récurrence du tri par fusion est : $$T(n) = 2T\!\left(\frac{n}{2}\right) + \Theta(n)$$ Par le théorème maître (cas 2 : $f(n) = \Theta(n^{\log_2 2}) = \Theta(n)$) : $$T(n) = \Theta(n \log n)$$

Cas	Complexité temporelle	Raison
Meilleur	Θ(n log n)	Division toujours en deux moitiés égales
Moyen	Θ(n log n)	Idem — indépendant de l'ordre initial
Pire	Θ(n log n)	Idem — pas de cas dégénéré
Espace	O(n)	Tableaux temporaires G et D dans fusion()

Explication intuitive — Θ(n log n) À chaque niveau de la récursion, on effectue Θ(n) opérations de fusion au total (chaque élément est copié exactement une fois). Il y a log₂ n niveaux (profondeur de l'arbre de récursion), d'où le total Θ(n log n).

Comparaison avec d'autres algorithmes de tri

Algorithme	Meilleur	Moyen	Pire	Espace	Stable
Tri fusion	Θ(n log n)	Θ(n log n)	Θ(n log n)	O(n)	Oui
Tri rapide	Θ(n log n)	Θ(n log n)	Θ(n²)	O(log n)	Non
Tri bulles	Θ(n)	Θ(n²)	Θ(n²)	O(1)	Oui
Tri insertion	Θ(n)	Θ(n²)	Θ(n²)	O(1)	Oui
Tri tas	Θ(n log n)	Θ(n log n)	Θ(n log n)	O(1)	Non

Quand utiliser le tri par fusion ?Le tri par fusion est idéal quand :

On a besoin d'un tri stable (conserve l'ordre relatif des éléments égaux).
On trie des listes chaînées (la fusion est O(1) en espace pour les listes).
On travaille avec de grands ensembles de données stockés sur disque (tri externe).
On veut garantir Θ(n log n) dans tous les cas (contrairement au tri rapide).

Inconvénient : il nécessite O(n) mémoire supplémentaire (vs O(1) pour le tri en place).

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Précédent Algorithmes de tri élémentaires (Tri sélection, tri par …

Suivant Algorithme de tri rapide

Discussion (0)

Soyez le premier à laisser un commentaire !

Laisser un commentaire

Votre commentaire sera visible après modération.

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

algorithme de tri par fusion

Tri par fusion — Merge Sort