let rec insert (e : int) (l : int list) =
  match l with
  | [] -> [e]
  | hd :: tl ->
      if e <= hd then
        e :: hd :: tl
      else
        hd :: insert e tl
let rec sort l =
  match l with
  | [] -> []
  | hd :: tl -> insert hd (sort tl)

(* running trace on insert and sort in the toplevel
 * give us a good illustration of how these functions
 * work
utop # sort;;
- : int list -> int list = <fun>

utop # sort [3;6;1;19;15];;
sort <-- [3; 6; 1; 19; 15]
sort <-- [6; 1; 19; 15]
sort <-- [1; 19; 15]
sort <-- [19; 15]
sort <-- [15]
sort <-- []
sort --> []
insert <-- 15
insert --> <fun>
insert* <-- []
insert* --> [15]
sort --> [15]
insert <-- 19
insert --> <fun>
insert* <-- [15]
insert <-- 19
insert --> <fun>
insert* <-- []
insert* --> [19]
insert* --> [15; 19]
sort --> [15; 19]
insert <-- 1
insert --> <fun>
insert* <-- [15; 19]
insert* --> [1; 15; 19]
sort --> [1; 15; 19]
insert <-- 6
insert --> <fun>
insert* <-- [1; 15; 19]
insert <-- 6
insert --> <fun>
insert* <-- [15; 19]
insert* --> [6; 15; 19]
insert* --> [1; 6; 15; 19]
sort --> [1; 6; 15; 19]
insert <-- 3
insert --> <fun>
insert* <-- [1; 6; 15; 19]
insert <-- 3
insert --> <fun>
insert* <-- [6; 15; 19]
insert* --> [3; 6; 15; 19]
insert* --> [1; 3; 6; 15; 19]
sort --> [1; 3; 6; 15; 19]
- : int list = [1; 3; 6; 15; 19]
 *)