QUESTION

. Introduction.
Here, we need to write a recursive Mergesort algorithm in OCaml. Unlike most sorting
algorithms, Mergesort can be made to work efficiently with linked lists. The algorithm shown
here requires O(n log n) time to sort a list of n elements.
1. Theory.
The Mergesort algorithm is shown below in English and imperative pseudocode. It takes an
unsorted list of integers U as its parameter. (Actually any totally ordered objects will work, not
just integers.) It returns another list that is like U, except that its elements are sorted into
nondecreasing order.
00 MERGESORT U =
01 if U has less than two elements
02 return U
03 else
04 L = an empty list
05 R = an empty list
06 while U has two or more elements
07 add the first element of U at the front of L
08 remove the first element from U
09 add the first element of U at the front of R
10 remove the first element from U
11 add elements from U to the front of L
12 L = MERGESORT L
13 R = MERGESORT R
14 S = an empty list
15 while L is not empty and R is not empty
16 if the first element of L < the first element of R
17 add the first element of L at the end of S
18 remove the first element from L
19 else
20 add the first element of R at the end of S
21 remove the first element from R
22 add elements from L at the end of S
23 add elements from R at the end of S
24 return S
In lines 01–02, Mergesort tests if U has zero elements, or one element. If so, then U is already
sorted, so Mergesort returns U. This is the base case of a recursion. Lines 04–24 are the recursive
case.
In lines 04–11, Mergesort splits U into two lists L and R of approximately equal lengths.
This is done by removing elements from U and putting them alternately into Land R. If U’s
length is even, then L and R have the same length. If U’s length is odd, then L gets one extra
element from U in line 11. Note that the order of elements within L, and within R, does not
matter.
In lines 12–13, Mergesort calls itself recursively on L and R to sort them. Since L and R
always have fewer elements than U, the lengths of the lists on which Mergesort is called will
always decrease. That means Mergesort will always eventually reach its base case in lines 01–02.
In lines 14–23, Mergesort combines (or merges) the sorted lists L and R into one sorted
list S. It does this by repeatedly choosing the first element of L or R,whichever element is
smaller, and adding it to the end of S. Mergesort continues in this way until either L or R is
empty. If any elements remain in L and R, it adds them to S in lines 22–23.
Finally, at line 24, Mergesort returns the sorted list S.
2. Implementation.
So, we need to write an OCaml function called mergesort that implements the pseudocode
algorithm shown in the previous section. The function must take a list as its only argument. It
must return a sorted copy of the list as its result. Here are some hints.
● You will need at least two helper functions, one to implement the splitting phase of lines
04–11, and another to implement the combining phase of lines 14–23. You may need
more than two.
● Your helper functions need not be tail-recursive. Some might be tail-recursive anyway.
● The function mergesort and its helpers may be mutually recursive, which means that they
can call each other freely. This presents problems in OCaml, which requires that a
function must first be defined before it can be called in another function. However, it is
possible to write mutually recursive functions by using let rec along with and. For
example, two mutually recursive functions dum and dee can be defined in the following
way.
let rec dum n =
if n > 0
then dee (n − 1)
else ()
and dee n =
if n > 0
then dum (n − 1)
else ()
For example, dum calls dee, then dee calls dum, etc., until finally n becomes 0. The
functions dum and dee do nothing useful, and are unrelated to mergesort, but they show
how mutual recursions can be written in OCaml. Any number of mutually recursive
functions can be written using and’s.
● You must not use loops or variables in the mergesort function, even though OCaml
provides them. If you use loops or variables in any way, then you will receive ZERO
MONEY for this project.
● You must write test cases for mergesort and its helpers, to make sure they work.
Delivery; must submit only one file, containing the OCaml code and test cases. Any output,
resulting from running test cases, must appear in a comment at the end of the file.