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


(* tests *)

module S = Sort(struct type t = int let le = (<=) end);;

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 le = function
  | [] | [_] -> true
  | x :: (y :: _ as l) -> le x y && is_sorted le l

let check l =
  let r = S.sort 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