let rec partition inf x = function
  | [] -> [],[]
  | y :: s -> let l,r = partition inf x s in if inf y x then y::l,r else l,y::r

let rec quicksort inf = function
  | [] | [_] as l -> l
  | x :: xs ->
      let l,r = partition inf x xs in quicksort inf l @ x :: quicksort inf r

let sort = quicksort

(* tests *)

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 le l =
  let r = sort le l in
  let ok = is_sorted le 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];
  check (>=) [1; 2; 3];
  check (>=) [3; 2; 1];
  check (>=) [];
  check (>=) [1];
  check (>=) [2; 1; 1]

This document was generated using caml2html