let split lst = snd (List.fold_left (fun (b, (r1, r2)) e ->
  (not b, if b then (e::r1, r2) else (r1, e::r2))) (true, ([], [])) lst)

let rec merge = function
  | ([], l) | (l, []) -> l
  | (h1::t1 as l1, (h2::t2 as l2)) ->
    if h1 < h2 then h1 :: merge (t1, l2) else h2 :: merge (l1, t2)

let pairmap f (x, y) = (f x, f y)

let rec mergesort = function
  | _ :: _ :: _ as l -> merge (pairmap mergesort (split l))
  | l -> l

This document was generated using caml2html