let rec insertion x = function
  | [] -> [x]
  | y :: _ as l when x <= y -> x :: l
  | y :: r -> y :: insertion x r

let rec insertion_sort = function
  | [] | [_] as l -> l
  | x :: l -> insertion x (insertion_sort l)


(* 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 = insertion_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