How would you write insertion sort in ocaml style?

Example from c beneath.
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;

/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;

Although it isn’t ideal, you can duplicate your C algorithm in OCaml. OCaml has mutable arrays, for loops, and all the rest. You can also do insertion sort in a more functional style.

If this is a homework assignment for you, I suggest that you work on it a while on your own, it will probably teach you more that way.

Hi, I don’t know whether it’s a good idea to provide a solution, I hope you will have searched by yourself before looking at this message. I am a beginner too, so I might have written something not so efficient, but that’s a solution I found without imperative features, if you want to practice your functional style !

I am using the insert sub-function to insert a new element at the right place in a list, using an accumulator for tail-recursion optimisation. The f sub-function processes the list and inserts each element in a sorted accumulator that I am keeping in the calls in order to use recursion efficiently.

let insertion_sort l =
let rec insert acc e = function
| [] -> List.rev_append acc [e]
| a :: r ->
if e < a then List.rev_append acc (e :: a :: r)
else insert (a :: acc) e r
in
let rec f sorted = function
| [] -> sorted
| a :: r -> f (insert [] a sorted) r
in
f [] l