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

let rec fusion = function
  | [], 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)

This document was generated using caml2html