Imperative and Functional Merge Sort in OCaml

So happy to be back!  The last two week I was running around seeing doctors, lab technicians, etc because I had a mysterious lump on my neck.  It’s still there, but they figured out that it’s nothing worrisome.  I’m so grateful!  I’ve always been healthy so this was really shocking.  I realized that when I’m healthy and able to learn is when *nothing* goes wrong, but there’s a trillion things that could have gone wrong!  I’m cherishing every moment that I’m living.  In the last few days, whenever I could, I was working on writing merge sort in OCaml.

Functional Merge Sort

Because the divide-and-conquer approach is recursive in nature, writing merge sort functionally is actually pretty straight forward!  I applied the techniques I learnt earlier: write multiple small, standalone functions that give one result each, and construct the algorithm using these functions:

1. Write the function merge which takes two sorted lists as arguments and merge them into one, following the pseudocode as described in chapter 2 of Introduction to Algorithms.  It was pretty straight forward to write.  As always I start with the main case and have to fine tune and specify the edge cases.
2. Write the functions splitodd and spliteven.  These functions take an unsorted list as an argument, and split it into its odd or even elements.  I couldn’t think of a way to split a list into two halves as described in the book.  Taking the odd or even elements out is a lot easier functionally.  At first, I was not satisfied with this solution because the run time depends on the length of the list.  But then I realized the run time is not longer because the pseudocode in the book also involves putting each element in a new list, after calculating which position to split the list.
3. Write the function merge_sort which takes the list to be sorted as an argument.  This is also straight forward to write.  Since the argument is an unsorted list, I know it should be passed to splitodd and spliteven to split into two lists.  I know the result of merge_sort has to be the result of merge, because it is the function that returns a sorted list.

Imperative Merge Sort (NB: see this post for an improved version)

This is the first time writing an algorithm functionally is obviously easier to me than writing it imperatively.  Even though the book provides an imperative pseudocode, translating it still requires tediously keeping track of the indexes. Moreover

• The program is more difficult to use because it takes not only the unsorted list as the argument, but also the index of the first element and the length of the array.
• It is also more difficult to debug:
  • The program takes more arguments and so more opportunity for mistakes.
  • The imperative nature requires defining an array every time because the array is sorted in place.
  • The error message seems to be less helpful.  Before I could get it working, I had a while loop that did not terminate.  In the functional version, I would have been given a stack overflow error.

The last point leads to an important lesson that I learnt in this exercise: make sure the condition for the while loop to run includes a variable that changes through the runs!  Otherwise, the while loop will not terminate because the condition is always met!

I was shocked that I ended up spending so much more time writing the imperative version than the functional version!  I really don’t see any advantage of imperative style programming for this algorithm.  If you do please enlighten me!