More on Imperative Merge Sort

I talked about how I wrote imperative merge sort in OCaml earlier.  I have been thinking about improving it because it was not as tidy as I’d like.  I learnt a few things in the process:

• Gain as much information as you can to debug.  E.g., it can help to print out intermediate results.  I figured out how my program did not terminate using this technique.  I print the values of p and r with the following:

  let rec merge_sort a p r =
    if p < r then   
      print_string ("p: ");
      print_int (p);
      print_string (" r: ");
      print_int (r);
      print_string ("\n");
      merge_sort a p ((p + r)/2);
      merge_sort a ((p + r)/2 + 1) r;
      merge a p ((p + r)/2) r
  ;;

  OCaml returns:

  1 r: 1
  1 r: 1
  1 r: 1
  1 r: 1
  1 r: 1
  ......
  Stack overflow during evaluation (looping recursion?).
  

  which is clearly very bizarre.  First, the expressions after the then binding should only be executed if p <  r!  Since p and r are both 1, why is OCaml printing them?  Second, why isn’t OCaml printing the string “p: “?  This leads me to the next point……

• Caml only executes the first expression after the binding then.  If you have more than one expression in your if …then statement, you need to put brackets around the expressions.  Even if you specify the else case, you still need to add brackets.  E.g.

  let rec merge_sort a p r =
    if p < r then 
      merge_sort a p ((p + r)/2);
      merge_sort a ((p + r)/2 + 1) r;
      merge a p ((p + r)/2) r
    else ()
  ;;
  

  returns a syntax error on else.  Adding brackets fixes it, and the below code runs without problem.

  let rec merge_sort a p r =
    if p < r then ( 
      merge_sort a p ((p + r)/2);
      merge_sort a ((p + r)/2 + 1) r;
      merge a p ((p + r)/2) r
    )
  ;;

   

• The difference between if…then and the while loop is that if…then only runs once if the condition holds.  The while loop runs whenever the condition is met, for as many times as the condition is met.

I’m much happier with this cleaner version of merge sort.  Are you?  If you can think of more improvement please do tell!