Let’s continue with tail recursion and folding (recollect our previous post. Let’s use those concepts to write insertion sort algorithm. In an earlier post we wrote a recursive implementation of insertion sort algorithm as below:

let rec insert x lst =
  match lst with
  | [] -> [x]
  | h::t ->
     if (x <= h) then x::h::t
     else h::(insert x t);;
let rec isort lst =
  match lst with
  | [] -> []
  | [x] -> [x]
  | h::t -> insert h (isort t)

Now, let’s write a tail recursive version of insertion sort. Let’s just call it tr_isort.

let tr_isort lst =
  let rec aux lst acc =
    match lst with
    | [] -> acc
    | h::t -> aux t (insert h acc)
  in
  aux lst [];;

Food for thought - is it possible to write a tail-recursive version of insert function that we used above? If yes, why don’t we try it. If no, why not?