OCaml merge sort

gistfile1.ml

let split_rev cut xs =
  let (_, f, s) =   
    List.fold_left  
    (fun (i, f, s) x ->
      if i < cut then (i + 1, x::f, s) else (i + 1, f, x::s))
    (0, [], []) xs  
  in
  (f, s)

let rec ms xs =
  let len = List.length xs in
  if len <= 1 then xs
  else begin
    let (l, r) = split_rev (len / 2) xs in
    let (l, r) = (ms l, ms r) in
    let rec merge a l r =
      match (l, r) with
      | (l, []) -> List.rev a @ l
      | ([], r) -> List.rev a @ r
      | (lhd::ltl, rhd::rtl) when lhd < rhd -> merge (lhd::a) ltl r
      | (lhd::ltl, rhd::rtl) -> merge (rhd::a) l rtl
    in
    merge [] l r
  end

let _ =
  Random.self_init ();
  let n = 400 in
  let xs =
    let rec loop i xs =
      if i >= n then xs else loop (i + 1) (Random.int n::xs)
    in
    loop 0 [] in
  let p xs =
    List.iter (fun x -> print_int x;
    print_string " ") xs;
    print_newline ()
  in
  print_endline "=== original values ===";
  p xs;
  print_endline "=== sorted values ===";
  p (ms xs)