### Project Description

We provide excellent assignment help in Ocaml

**0. 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 L and 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] *)

If any assignment help in OCAML programming and any complex task please message via **WHATSAPP or UPLOAD**

### Project Details

**Date**April 30, 2021**Tags**Functional programming, Ocaml programming help

Comments are closed.