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**If you have more than one expression in your*then*.*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 thatif the condition holds. The while loop runs whenever the condition is met, for as many times as the condition is met.*if…then*only runs once

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

## Leave a Reply