(* ===================================================== *) (* Apprentissage de la programmation avec OCaml *) (* Catherine Dubois & Valérie Ménissier-Morain *) (* Éditions Hermès Sciences *) (* Mars 2004 *) (* ===================================================== *) (* Fichier MLSRC/Tris_listes/fusion_liste.ml *) (* ===================================================== *)

let rec diviser_liste l = match l with | [] -> ([], []) | [x] -> ([x], []) | x1::x2::l' -> let (l1, l2) = diviser_liste l' in (x1::l1, x2::l2);; let rec fusion l1 l2 = match (l1, l2) with | ([], []) -> [] | ([], _) -> l2 | (_, []) -> l1 | (x1::l'1, x2::l'2) -> if x1 < x2 then x1::(fusion l'1 (x2::l'2)) else x2::(fusion (x1::l'1) l'2);; let rec tri_fusion l = match l with | [] -> [] | [x] -> [x] | _ -> let (l1, l2) = diviser_liste l in fusion (tri_fusion l1) (tri_fusion l2);;