(* Tri fusion *)
(* Version avec des tableaux *)
let division (t : 'a array) : 'a array * 'a array =
  let n = Array.length t in
  let g = Array.make (n / 2) t.(0) and
      d = Array.make (n - n / 2) t.(0) in
  for i = 0 to n / 2 - 1 do
    g.(i) <- t.(i)
  done ;
  for i = n / 2 to n - 1 do
    d.(i - n / 2) <- t.(i)
  done ;
  (g, d) ;;

(* On peut aussi utiliser Array.sub t pos len *)

Array.sub [|1; 2; 3; 4; 5; 6; 7|] 0 3;;
Array.sub [|1; 2; 3; 4; 5; 6; 7|] 3 4;;

let division (t : 'a array) : 'a array * 'a array =
  let n = Array.length t in
  let g = Array.sub t 0 (n / 2) and
      d = Array.sub t (n / 2) (n - n / 2) in
  (g, d) ;;

division [||] ;;
division [|1|] ;;

division [|1; 2; 3; 4; 5; 6; 7|] ;;
division [|1; 2; 3; 4; 5; 6; 7; 8|] ;;


let fusion (t1 : 'a array) (t2 : 'a array) : 'a array = 
  let n1 = Array.length t1 and n2 = Array.length t2 in
  let t = Array.make (n1 + n2) t1.(0) in
  let i1 = ref (0) and i2 = ref (0) in
  for i = 0 to (n1 + n2 - 1) do
    if !i1 = n1 then
      begin t.(i) <- t2.(!i2) ; incr i2 end
    else if !i2 = n2 then
       begin t.(i) <- t1.(!i1) ; incr i1 end
    else let (e1, e2) = (t1.(!i1), t2.(!i2)) in
     if e1 < e2 then
       begin  t.(i) <- e1 ; incr i1 end
      else begin t.(i) <- e2 ; incr i2 end
  done ;
  t ;;


fusion [|1; 5; 6; 8|] [|2; 3; 4; 9|] ;;

let rec tri_fusion (t : 'a array) : 'a array =
  let n = Array.length t in
  if n <= 1 then t
  else let (g, d) = division t in
       let (gt, dt) = (tri_fusion g, tri_fusion d) in
       fusion gt dt ;;

tri_fusion [|1; 4; 3; 2; 8; 10; 0; 5; 7|] ;;

(* Version avec des listes *)
let rec division_l (l : 'a list ) : 'a list * 'a list =
  match l with
  | [] -> [],  []
  | [e] -> [e], []
  | t1 :: t2 :: q -> let (lg, ld) = division_l q in
                     t1 :: lg, t2 :: ld ;;

division_l [1; 2; 3; 4; 5; 6; 7] ;;
division_l [1; 2; 3; 4; 5; 6; 7; 8] ;;

let rec fusion_l (l1 : 'a list) (l2 : 'a list) : 'a list =
  match l1, l2 with
  | [], [] -> []
  | _, [] -> l1
  | [], _ -> l2
  | t1 :: q1, t2 :: q2 -> if t1 < t2 then t1 :: fusion_l q1 l2
                          else t2 :: fusion_l l1 q2 ;;

fusion_l [1; 5; 6; 8] [2; 3; 4; 9] ;;  
fusion_l [1; 5] [2; 3; 4; 6; 8; 9] ;;

let rec tri_fusion_l (l : 'a list) : 'a list =
  match l with
  | [] -> []
  | [e] -> [e]
  | _ -> let (lg, ld) = division_l l in
         let (lgt, ldt) =(tri_fusion_l lg, tri_fusion_l ld) in
         fusion_l lgt ldt ;;

tri_fusion_l [1; 4; 3; 2; 8; 10; 0; 5; 7] ;;