Cet article explore les méthodes de tri par fusion pour orgnaiser une liste chaînée en ordre croissant. L'objectif est d'atteindre une complxeité temporelle de O(n log n) avec une complexité spatiale auxiliaire constante (O(1)), ce qui implique de réorganiser les pointeurs des nœuds existants plutôt que de créer de nouveaux nœuds lors de la fusion.

Tri par Fusion de Haut en Bas (Récursif)

Le tri par fusion récursif, ou de haut en bas, applique la stratégie classique "diviser pour régner" :

1. Division : La liste chaînée est divisée en deux sous-listes de tailles approximativement égales. Une méthode courante pour cela est d'utiliser deux pointeurs (lent et rapide) pour identifier le point médian.
2. Récursion : Les deux sous-listes obtenues sont ensuite triées de manière récursive.
3. Fusion : Une fois que les sous-listes sont triées individuellement, elles sont combinées pour former une seule liste triée.

La condition d'arrêt de la récursion est atteinte lorsqu'une sous-liste contient zéro ou un élément, car elle est intrinsèquement considérée comme triée.

Implémentation C++

/**
 * Definition pour un nœud de liste chaînée.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x, next) {}
 * };
 */
class Solution {
public:
    // Fonction utilitaire pour fusionner deux listes chaînées triées, en O(1) espace auxiliaire
    ListNode* fusionnerListes(ListNode* liste1, ListNode* liste2) {
        ListNode teteFictive; // Nœud factice pour simplifier la gestion de la tête de la liste fusionnée
        ListNode* pointeurCourant = &teteFictive;

        while (liste1 != nullptr && liste2 != nullptr) {
            if (liste1->val <= liste2->val) {
                pointeurCourant->next = liste1;
                liste1 = liste1->next;
            } else {
                pointeurCourant->next = liste2;
                liste2 = liste2->next;
            }
            pointeurCourant = pointeurCourant->next;
        }

        // Attacher le reste de la liste non vide (s'il y en a une)
        if (liste1 != nullptr) {
            pointeurCourant->next = liste1;
        } else if (liste2 != nullptr) {
            pointeurCourant->next = liste2;
        }

        return teteFictive.next; // Retourne le début de la liste réellement fusionnée
    }

    // Fonction principale récursive pour trier la liste chaînée
    ListNode* trierRecursivement(ListNode* tete) {
        // Cas de base : liste vide ou un seul élément est déjà triée
        if (tete == nullptr || tete->next == nullptr) {
            return tete;
        }

        // Trouver le milieu de la liste en utilisant la méthode des deux pointeurs
        ListNode* lent = tete;
        ListNode* rapide = tete;
        ListNode* preLent = nullptr; // Pointeur pour marquer le nœud juste avant 'lent' pour la division

        while (rapide != nullptr && rapide->next != nullptr) {
            preLent = lent;
            lent = lent->next;
            rapide = rapide->next->next;
        }

        // Casser la liste en deux parties au milieu
        if (preLent != nullptr) {
            preLent->next = nullptr;
        }

        // Trier récursivement les deux moitiés
        ListNode* moitieGaucheTriee = trierRecursivement(tete);
        ListNode* moitieDroiteTriee = trierRecursivement(lent);

        // Fusionner les deux moitiés triées
        return fusionnerListes(moitieGaucheTriee, moitieDroiteTriee);
    }

    ListNode* sortList(ListNode* head) {
        return trierRecursivement(head);
    }
};

Tri par Fusion de Bas en Haut (Itératif)

Le tri par fusion de bas en haut est une approche itérative qui élimine la surcharge liée à la récursion et garantit une complexité spatiale auxiliaire strictement constante. Il procède en fusionnant successivement des sous-listes de taille croissante (1, puis 2, 4, etc.) jusqu'à ce que l'intégralité de la liste soit triée.

Les étapes principales sont les suivantes :

1. Déterminer la longueur totale N de la liste chaînée.
2. Initialiser une taille de segment tailleSegment à 1, et la doubler à chaque itération du processus de tri (1, 2, 4, ..., jusqu'à N/2).
3. Dans chaque itération, parcourir la liste et identifier des paires de segments consécutifs, chacun de longueur tailleSegment.
4. Fusionner chaque paire de segments triés en utilisant une logique de fusion qui ne crée pas de nouveaux nœuds (O(1) espace).
5. Gérer méticuleusement les pointeurs pour releir correctement les segments fusionnés à la structure principale de la liste.

Quatre pointeurs clés sont généralement nécessaires pour implémenter efficacement cette approche :

• precedent : Pointe vers la fin de la sous-liste déjà traitée, servant de point d'attache pour le segment nouvellement fusionné.
• segment1 : Le début du premier segment à fusionner.
• segment2 : Le début du second segment à fusionner.
• segmentSuivant : Le début de la portion de la liste qui n'a pas encore été traitée.

Implémentation C++

/**
 * Definition pour un nœud de liste chaînée.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x, next) {}
 * };
 */
class Solution {
public:
    // Fonction utilitaire pour fusionner deux listes chaînées triées (réutilisation)
    ListNode* fusionnerListes(ListNode* liste1, ListNode* liste2) {
        ListNode teteFictive;
        ListNode* pointeurCourant = &teteFictive;

        while (liste1 != nullptr && liste2 != nullptr) {
            if (liste1->val <= liste2->val) {
                pointeurCourant->next = liste1;
                liste1 = liste1->next;
            } else {
                pointeurCourant->next = liste2;
                liste2 = liste2->next;
            }
            pointeurCourant = pointeurCourant->next;
        }

        if (liste1 != nullptr) {
            pointeurCourant->next = liste1;
        } else if (liste2 != nullptr) {
            pointeurCourant->next = liste2;
        }

        return teteFictive.next;
    }

    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        // 1. Calculer la longueur totale de la liste
        int longueur = 0;
        ListNode* curseur = head;
        while (curseur != nullptr) {
            longueur++;
            curseur = curseur->next;
        }

        ListNode teteFictiveGlobale(0); // Nœud factice pour gérer facilement le début de la liste globale
        teteFictiveGlobale.next = head;

        // Itérer avec une taille de segment (taille de fusion) qui double à chaque pas
        for (int tailleSegment = 1; tailleSegment < longueur; tailleSegment <<= 1) {
            ListNode* precedent = &teteFictiveGlobale; // Pointeur pour attacher les segments fusionnés
            curseur = teteFictiveGlobale.next; // Réinitialiser le curseur au début de la liste non traitée pour cette 'tailleSegment'

            while (curseur != nullptr) {
                // 2. Isoler le premier segment (liste1)
                ListNode* liste1 = curseur;
                for (int i = 1; i < tailleSegment && curseur != nullptr; ++i) {
                    curseur = curseur->next;
                }

                // Si curseur est null ici, liste1 est le dernier segment ou est trop court. Pas de liste2.
                if (curseur == nullptr) {
                    precedent->next = liste1; // Attacher directement le reste
                    break;
                }
                
                // 3. Isoler le second segment (liste2)
                ListNode* liste2 = curseur->next;
                curseur->next = nullptr; // Casser la liaison entre liste1 et liste2
                
                curseur = liste2; // Déplacer curseur au début de liste2
                for (int i = 1; i < tailleSegment && curseur != nullptr; ++i) {
                    curseur = curseur->next;
                }

                // 4. Déterminer le début du segment suivant non traité (segmentSuivant)
                ListNode* segmentSuivant = nullptr;
                if (curseur != nullptr) {
                    segmentSuivant = curseur->next;
                    curseur->next = nullptr; // Casser la liaison entre liste2 et segmentSuivant
                }

                // 5. Fusionner les deux segments
                ListNode* segmentFusionne = fusionnerListes(liste1, liste2);

                // 6. Attacher le segment fusionné à la liste principale
                precedent->next = segmentFusionne;

                // 7. Avancer 'precedent' jusqu'à la fin du segment nouvellement fusionné
                while (precedent->next != nullptr) {
                    precedent = precedent->next;
                }

                // 8. Préparer pour la prochaine itération : déplacer le curseur au segment suivant non traité
                curseur = segmentSuivant;
            }
        }

        return teteFictiveGlobale.next; // La liste triée commence après le nœud factice
    }
};