Principe du tri par fusion

Le tri par fusion (Merge Sort) repose sur le paradigme « diviser pour régner ». Le tableau est divisé récursivement en sous-tableaux jusqu'à obtenir des éléments isolés, puis ces sous-tableaux sont fusionnés de manière ordonnée pour reconstituer un tableau entièrement trié.

Implémentation récursive

L'approche récursive consiste à :

• Calculer le point médian du segment courant via centre = debut + (fin - debut) / 2
• Appeler récursivement la fonction sur la moitié gauche [debut, centre]
• Appeler récursivement la fonction sur la moitié droite [centre + 1, fin]
• Fusionner les deux moitiés désormais ordonnées à l'aide d'un tableau temporaire

void fusionner(int* tableau, int debut, int fin, int* tampon)
{
    if (debut >= fin)
        return;

    int centre = debut + (fin - debut) / 2;

    fusionner(tableau, debut, centre, tampon);
    fusionner(tableau, centre + 1, fin, tampon);

    int gauche = debut;
    int droite = centre + 1;
    int pos = debut;

    while (gauche <= centre && droite <= fin)
    {
        if (tableau[gauche] <= tableau[droite])
            tampon[pos++] = tableau[gauche++];
        else
            tampon[pos++] = tableau[droite++];
    }

    while (gauche <= centre)
        tampon[pos++] = tableau[gauche++];

    while (droite <= fin)
        tampon[pos++] = tableau[droite++];

    for (int k = debut; k <= fin; k++)
        tableau[k] = tampon[k];
}

void triFusion(int* tableau, int taille)
{
    int* tampon = (int*)malloc(sizeof(int) * taille);
    if (tampon == NULL)
    {
        perror("Échec d'allocation");
        exit(EXIT_FAILURE);
    }
    fusionner(tableau, 0, taille - 1, tampon);
    free(tampon);
}

Complexité temporelle : O(n log n) dans tous les cas. La profondeur de récursion est log n et chaque niveau effectue un travail linéaire.

Implémentation itérative (non récursive)

La version itérative procède de bas en haut. Au lieu de diviser récursivement, on commence avec des sous-tableaux de taille 1, puis on les fusionne par paires, en doublant la taille à chaque passage.

Points clés :

• pas démarre à 1 et double à chaque itération
• À chaque tour, on fusionne des blocs adjacents de longueur pas
• Il faut gérer attentivement les dépassements de frontières lorsque la taille du tableau n'est pas une puissance de 2

void triFusionIteratif(int* tableau, int taille)
{
    int* tampon = (int*)malloc(sizeof(int) * taille);
    if (!tampon)
    {
        perror("Échec d'allocation");
        exit(EXIT_FAILURE);
    }

    int pas = 1;
    while (pas < taille)
    {
        for (int i = 0; i < taille; i += 2 * pas)
        {
            int debutG = i;
            int finG = i + pas - 1;
            int debutD = i + pas;
            int finD = i + 2 * pas - 1;

            if (debutG >= taille)
                break;
            if (finG >= taille)
                finG = taille - 1;
            if (debutD >= taille)
                continue;
            if (finD >= taille)
                finD = taille - 1;

            int g = debutG, d = debutD, idx = debutG;

            while (g <= finG && d <= finD)
            {
                if (tableau[g] <= tableau[d])
                    tampon[idx++] = tableau[g++];
                else
                    tampon[idx++] = tableau[d++];
            }
            while (g <= finG)
                tampon[idx++] = tableau[g++];
            while (d <= finD)
                tampon[idx++] = tableau[d++];

            memcpy(tableau + debutG, tampon + debutG,
                   sizeof(int) * (finD - debutG + 1));
        }
        pas *= 2;
    }
    free(tampon);
}

Comparaison des performances

Pour évaluer les performances, on génère un tableau aléatoire de 100 000 entiers et on chronomètre chaque algorithme :

void comparerTri()
{
    srand((unsigned)time(NULL));
    const int N = 100000;

    int* base = (int*)malloc(sizeof(int) * N);
    for (int i = 0; i < N; i++)
        base[i] = rand();

    int* copie = (int*)malloc(sizeof(int) * N);

    memcpy(copie, base, sizeof(int) * N);
    clock_t t1 = clock();
    triFusion(copie, N);
    clock_t t2 = clock();
    printf("Tri par fusion (recursif) : %ld ms\n", t2 - t1);

    memcpy(copie, base, sizeof(int) * N);
    t1 = clock();
    triFusionIteratif(copie, N);
    t2 = clock();
    printf("Tri par fusion (iteratif) : %ld ms\n", t2 - t1);

    free(base);
    free(copie);
}

Les résultats montrent que le tri par fusion se classe parmi les algorithmes les plus performants, au même niveau que le tri rapide, le tri de Shell et le tri par tas. La complexité garantie en O(n log n), y compris dans le pire des cas, constitue un avantage majeur par rapport au tri rapide, dont la performence peut dégrader en O(n²).