module Sort(X : sig type t val le : t -> t -> bool end) : sig
  val sort : X.t list -> X.t list
end = struct

  let rec partition x = function
    | [] -> [],[]
    | y :: s -> let l,r = partition x s in if X.le y x then y::l,r else l,y::r
        
  let rec sort = function
    | [] | [_] as l -> l
    | x :: xs -> let l,r = partition x xs in sort l @ x :: sort r

end;;

module S = Sort(struct type t = int let le = (<=) end);;
S.sort [1;2;3;2;4;1];;

This document was generated using caml2html