Fusionner deux listes triées

Exercice · OCaml (option informatique), chapitre 9 — Algorithmique : les tris

Énoncé

Écrire fusion l1 l2 et l'appliquer à fusion [1; 4] [2; 3; 5].

Corrigé

let rec fusion l1 l2 =
  match l1, l2 with
  | [], _ -> l2
  | _, [] -> l1
  | x :: r1, y :: r2 ->
      if x <= y then x :: fusion r1 l2
      else y :: fusion l1 r2

fusion [1;4] [2;3;5] : $1 \leq 2$ → 1 :: fusion [4] [2;3;5] ; $4 > 2$ → 1 :: 2 :: fusion [4] [3;5] ; $4 > 3$ → ... 3 :: fusion [4] [5] ; $4 \leq 5$ → [1; 2; 3; 4; 5].

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.