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

Learning
1

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];
2

(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
  ...
```
3

Fixed, now would you like to help me?

4

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, ^^

5

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?

6

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

3 Likes
7

No, sorry I dont comprehend.