Comment fusionner deux listes déjà triées dans le tri fusion ?

Réponse courte

Compare les premières valeurs encore disponibles dans les deux listes, ajoute la plus petite au résultat et avance son indice. Quand une liste est épuisée, recopie la fin de l’autre, déjà triée.

Comprendre

Deux indices et une liste résultat

La fusion reçoit deux listes ordonnées par ordre croissant. Place un indice au début de chacune et initialise une liste résultat vide. Tant qu’il reste des valeurs dans les deux listes, compare celles que désignent les indices. Ajoute la plus petite au résultat et avance uniquement l’indice de la liste choisie.

Terminer quand une liste s’épuise

La boucle de comparaison cesse dès qu’une liste n’a plus de valeur. Les éléments qui restent dans l’autre sont déjà ordonnés : ajoute-les à la suite du résultat. Ainsi, chaque élément des deux listes d’entrée est recopié une fois, sans être perdu.

Dérouler un exemple

Fusionne [2, 7] et [1, 5]. Compare 2 et 1, puis ajoute 1. Compare ensuite 2 et 5, ajoute 2, puis compare 7 et 5 et ajoute 5. La première liste contient encore 7 ; la seconde est épuisée. Ajoute 7 : la fusion donne [1, 2, 5, 7].

Préserver doublons et stabilité

Ne supprime pas les valeurs égales : deux occurrences restent deux éléments. Si l’on veut une fusion stable, choisis la valeur de la liste gauche en cas d’égalité, à condition que les tris précédents soient stables eux aussi. Une confusion d’indice peut faire oublier un élément ou ajouter deux fois le même.

Étapes

  1. Crée les indices i et j au début des deux listes, puis un résultat vide.
  2. Tant que les deux listes ont une valeur disponible, compare-les.
  3. Ajoute la plus petite valeur et augmente seulement l’indice correspondant.
  4. Quand une liste est épuisée, ajoute toutes les valeurs restantes de l’autre.

Exemples

  • Fusionner [2, 7] et [1, 5] produit [1, 2, 5, 7].
  • Fusionner [2, 4, 4] et [1, 4, 6] donne [1, 2, 4, 4, 4, 6] : les trois occurrences de 4 sont conservées.

Pièges fréquents

  • Avancer les deux indices après avoir ajouté une seule valeur : cela saute un élément qui n’a pas été copié.
  • Arrêter la fusion dès qu’une liste est vide sans recopier l’autre : les valeurs restantes manquent alors au résultat.

Et maintenant ?

Questions proches

← Toutes les questions-réponses