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

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


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

let check l =
 let r = quicksort 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