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)

This document was generated using caml2html