Info_MPSI/test2/DM1.ml

let fusion t l m u =
  let aux = Array.make (u-l+1) t.(0) and i = ref l
  and j = ref (m+1) and k = ref 0 in
  
  while (!i <= m) && (!j <= u) do
    if (t.(!i) <= t.(!j))
      then
        begin
      aux.(!k) <- t.(!i);
      i := !i + 1
    end
  else
    begin
      aux.(!k) <- t.(!j);
      j := !j + 1
    end;
    k := !k + 1
  done;
  while (!i <= m) do
    aux.(!k) <- t.(!i);
    i := !i + 1;
    k := !k + 1
  done;
  while (!j <= u) do
    aux.(!k) <- t.(!j);
    j := !j + 1;
    k := !k + 1
  done;
  for x=0 to (!k-1) do
    t.(l+x) <- aux.(x)
  done
;;

let tri_fusion t =
  let rec tri_fusion_aux t l u =
    if (l < u) then
      begin
        let m = (l+u)/2 in
        tri_fusion_aux t l m;
        tri_fusion_aux t (m+1) u;
        fusion t l m u;
      end
    in tri_fusion_aux t 0 (Array.length t - 1)
;;