I wrote the insertion algorithm in both imperative and functional styles in OCaml! I talk about the fun and challenges of each style below:

### Imperative Insertion Sort

I strictly follow the pseudocode on p.18 of the book Introduction to Algorithms. The pseudocode is in imperative style so all I need to do is to translate the code into suitable OCaml syntax. A few things to note:

- Capital letters are reserved for module names. I cannot use a capital letter for the array argument like in the code. (I mentioned it here but now I really know!)
- In OCaml, array indexes starts from 0, which is different from the book which starts from 1.
- From the OCaml manual, I learn that to call the length of an array, the syntax is

*Array.length arrayName* - I translate the counter
in the pseudocode to a*i*in OCaml, which can be easily called and update.**ref**

And that’s it! Pretty simple! Thanks to OCaml’s imperative features. Writing it in functional style is a bit more challenging.

### Functional Style Insertion Sort

Because the pseudocode is in imperative style, translating it to functional OCaml takes more thoughts. Instead of an array, the list of numbers (or chars or strings or bool) to be sorted is of type * ‘a list*. And I run the algorithm using list operators.

I start with the inner recursive function ** insert**, which corresponds to the

**loop of the pseudocode.**

*while*let rec insert s h = match s with shd :: stl -> if shd > h then h :: shd :: stl else shd :: insert stl h |_ -> [h]

Instead of calling each element by position like the *while* loop, *insert* is a function that takes two arguments, a sorted list, ** s** and an element that is to be inserted in the right position,

*. The function recursively compares the element with the (partial) sorted list head,*

**h****and the rest of the sorted list,**

*shd,***is recursed to the next comparison. The recursion**

*stl,***terminates**when either

is smaller than an element of the sorted list and is inserted in front of an element of the sorted list. Or*h*is compared to the last element of the sorted list and is bigger than that element. The second match case. The last element of the sorted list is*h*to the list that contains the single element*cons*.*h*

Originally I also included the match case of *s* having only one element, and OCaml nicely warned me that that match case was never used because it can still match the first case even when *stl* is an empty list.

Once I verify that *insert* works, I move on to the recursive function ** sort**, which takes a list,

**(which is to be sorted) as an argument.**

*l**sort*takes out an element of the given list,

**to be compared in**

*hd**. Similar to the for loop in the pseudocode.*

**insert**match l with [] -> [] | hd :: tl -> insert (sort tl ) hd

I knew the result of *sort* has to be the result of *insert*, comparing with the ** hd** of the given list each time. But at first I wasn’t sure how to give

*insert*a sorted list recursively. I thought it has to be something like

*insert (insert something something) hd*. But then I realized that’s what sort is for! It recurses

*insert*!

Of course, I include the **termination** for this recursive function (the first match case), which also catches the boundary case of when the given list is empty.

Woohoo! It’s so exciting every time I see a program that I wrote works!

## Leave a Reply