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:

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);;


(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)


|h::t -> insert h t

Do you see the implication?

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


No, sorry I dont comprehend.