22. Merge Sort : Implémentation et Étape de Fusion (Partie 2)

Le cœur de l'efficacité du Merge Sort réside dans la fonction merge, qui prend deux sous-listes triées et les combine en une seule liste triée en temps O(N).

La Fonction Merge

Imaginez combiner deux jeux de cartes, tous deux déjà triés. Il vous suffit de regarder la carte supérieure de chaque paquet et de choisir la plus petite à ajouter au paquet final.

1. Utiliser deux pointeurs, un pour le début de la sous-liste gauche (L) et un pour le début de la sous-liste droite (R).
2. Tant que les deux sous-listes ont des éléments, comparer les éléments pointés.
3. Copier l'élément le plus petit dans le tableau final et avancer son pointeur.
4. Une fois qu'une sous-liste est épuisée, copier tous les éléments restants de l'autre sous-liste.

Analyse de l'Efficacité

• Complexité Temporelle : O(N log N) pour le pire, le moyen et le meilleur cas.
  • log N provient de la phase de 'division' (combien de fois nous divisons la liste en deux).
  • N provient de la phase de 'fusion' (nous examinons chaque élément une fois à chaque niveau de fusion).
• Complexité Spatiale : Espace auxiliaire O(N), car il nécessite un tableau temporaire pour effectuer la fusion.