# Can someone explain how this recursion is working for insertion sort?

I have justt created my insertion sort which works fine, but I don’t understand how the recursion works.

How can 1 end up being the first element?

This is how I see the algortihm:
[5;2;17;16;1]
[2;5;17;17;1]

It stops there since 5 < 17?

``````let insert elem l1 =
match l1 with
[] -> [elem]
|x::l ->
if x < elem
then x::insert elem l
else elem::x::l;;

let rec sort l2 =
match l2 with
[] -> []
|h::t -> insert h (sort t);;

sort[5;2;17;16;1];``````

(Can you edit your post and wrap your code in triple backticks so that your code is properly formatted?)

`````````
let insert elem l1 =
match l1 with
...
```
``````

Fixed, now would you like to help me?

You seem to be missing a `rec` annotation on your `insert` function, which means the call at line 6 probably uses another already defined `insert` function if your example compiles correctly.

Once `insert` is properly declare as recursive, your code seems correct on your example, ^^

First: you can trace the calls by adding some printfs in your code.

Second: the last line of sort is

``````|h::t -> insert h (sort t)
``````

not

``````|h::t -> insert h t
``````

Do you see the implication?

Shouldn’t people be asking their teaching assistant or professor for help with homework?

3 Likes

No, sorry I dont comprehend.