Imperative and Functional Insertion Sort in OCaml

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 i in the pseudocode to a ref in OCaml, which can be easily called and update.

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 while loop of the pseudocode.

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, h.  The function recursively compares the element with the (partial) sorted list head, shd, and the rest of the sorted list, stl, is recursed to the next comparison. The recursion terminates when either

• h 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 cons to the list that contains the single element 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, l (which is to be sorted) as an argument.  sort takes out an element of the given list, hd to be compared in insert.  Similar to the for loop in the pseudocode.

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!