let rec split = function
  | [] -> [], []
  | x :: r -> let l1,l2 = split r in x :: l2, l1

let rec fusion l1 l2 = match l1, l2 with
  | [], l | l, [] -> l
  | x1 :: r1, (x2 :: _ as l2) when x1 <= x2 -> x1 :: fusion r1 l2
  | l1, x2 :: r2 -> x2 :: fusion l1 r2

let rec mergesort = function
  | [] | [_] as l -> l
  | l -> let l1,l2 = split l in fusion (mergesort l1) (mergesort l2)


(* tests *)

let rec print fmt = function
 | [] -> ()
 | [x] -> Format.fprintf fmt "%d" x
 | x :: l -> Format.fprintf fmt "%d, %a" x print l

let rec is_sorted = function
 | [] | [_] -> true
 | x :: (y :: _ as l) -> x <= y && is_sorted l

let check l =
 let r = mergesort l in
 let ok = is_sorted r in
 Format.printf "[%a] => [%a]: %s@."
   print l print r (if ok then "OK" else "FAILED");
 if not ok then exit 1

let () =
 check [1; 2; 3];
 check [3; 2; 1];
 check [];
 check [1];
 check [2; 1; 1]

This document was generated using caml2html