21. Merge Sort (Tri par Fusion) : L'Approche Diviser pour Régner (Partie 1)
Le Merge Sort est le premier algorithme O(N log N) que nous couvrons, représentant un bond majeur en efficacité pour les grandes données.
Paradigme : Diviser pour Régner (Divide and Conquer)
Le Merge Sort est un exemple classique du paradigme Diviser pour Régner :
- Diviser : Décomposer le problème (la liste) en deux ou plusieurs sous-problèmes plus petits (sous-listes) de manière récursive.
- Régner (Conquer) : Résoudre les sous-problèmes de manière récursive. Si la sous-liste est suffisamment petite (par exemple, taille 0 ou 1), le problème est trivial.
- Combiner (Merge) : Combiner les solutions des sous-problèmes pour résoudre le problème original.
Étapes du Merge Sort
- Diviser : Fractionner continuellement le tableau en moitiés jusqu'à ce que vous ayez N sous-listes, chacune contenant un seul élément.
- Fusionner (Merge - La Partie Difficile) : Fusionner à plusieurs reprises les sous-listes pour produire de nouvelles sous-listes triées jusqu'à ce qu'il ne reste qu'une seule liste triée.