### Project Description

# 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.

**let rec merge l r =**

**match (l,r) with**

**| ([],_) -> r**

**| (_,[]) -> l**

**| (x :: tl, y :: tr) ->**

**if x < y**

**then (x :: (merge tl r))**

**else (y :: (merge l tr))**

**and split u =**

**let rec aux u l r =**

**match u with**

**| [] -> (l, r)**

**| x :: tu -> aux tu r (x :: l)**

**in (aux u [] [])**

**and mergesort u =**

**match u with**

**| []**

**| _ :: [] -> u**

**| _ -> let (l,r) = (split u) in**

**(merge (mergesort l) (mergesort r));;**

**(* PRINT THINGS. Print a list of THINGS using a FORMAT string. *)**

**let printThings format things =**

**let rec printingThings things =**

**match things**

**with [] -> () |**

**firstThing :: otherThings ->**

**Printf.printf ” ; ” ;**

**Printf.printf format firstThing ;**

**printingThings otherThings**

**in Printf.printf “[” ;**

**(match things**

**with [] -> () |**

**firstThing :: otherThings ->**

**Printf.printf format firstThing ;**

**printingThings otherThings) ;**

**Printf.printf “]\n” ;;**

**(* Test *)**

**Printf.printf “split:\n”;;**

**let a, b = (split [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]);;**

**printThings “%i” a;; (* even number [8; 6; 4; 2; 0] *)**

**printThings “%i” b;; (* odd number [9; 7; 5; 3; 1] *)**

**Printf.printf “\nmerge:\n”;;**

**let x = (merge a b);;**

**printThings “%i” x;; (* [8; 6; 4; 2; 0; 9; 7; 5; 3; 1] *)**

**Printf.printf “\nmergesort:\n”;;**

**let y = (mergesort x);;**

**printThings “%i” y;; (* [0; 1; 2; 3; 4; 5; 6; 7; 8; 9] *)**

### Project Details

**Date**November 16, 2021**Tags**Functional programming, Ocaml programming help, Programming

Comments are closed.