Prolog $(30$ Points$)$

$($NOTE: Below we are using Prolog notation. Variables are Uppercase. Constants are lowercase.$)$

In class I showed how $2$ sorted$-$lists can be merged in a sorted fashion. That means we are so close to implementing merge$-$sort! We will implement merge$-$sort below.

Example output:

mergeSort$([],$L$).$

L $=[]$

mergeSort$([2],$L$).$

L $=[2]$

mergeSort$([4,2,3,1],$L$).$

L $=[1,2,3,4]$

mergeSort$([5,4,6,2,7,3,1,8],$L$).$

L $=[1,2,3,4,5,6,7,8]$

Our program will be implemented with $5$ predicates:

mergeSort$/2$: which in comes an unsorted list, out goes the sorted list.

merge$/3$: which merges the

split$2$ways$/3$:

insertIn$1/5$ and insertIn$2/5$:

So let us go$!$

Finish mergeSort$/2$:

mergeSort$([],[])$ :$-!.\%\%$ Base case when list is empty

mergeSort$([$X$],[$X$])$ :$-!.\%\%$ Base case when list has only $1$ item

$\%\%$ YOUR CODE TO HANDLE GENERAL CASE

$\%\%(1)$ Split the in coming list into $2$ sublists

$\%\%(2)$ Recursively sort both lists

$\%\%(3)$ Merge both lists into the output list

Here is all the code for merge$/3.$

$($This is all of it$,$ there is nothing else to add.$)$

merge$([],$L$,$L$).$

merge$($L$,[],$L$).$

merge$([$F$0|$R$0],[$F$1|$R$1],[$F$0|$L$])$ :$-$

$($F$0<$ F$1),$

merge$($R$0,[$F$1|$R$1],$L$).$

merge$([$F$0|$R$0],[$F$1|$R$1],[$F$1|$L$])$ :$-$

$($F$0>=$ F$1),$

merge$([$F$0|$R$0],$R$1,$L$).$

Here is all the code for split$2$ways$/3.$

$($This is all of it$,$ there is nothing else to add.$)$

split$2$ways$($Original$,$R$1,$R$2)$ :$-$

insertIn$1($Original$,[],[],$R$1,$R$2).$

You must finish the predicates

insertIn$1()($insertIn$1/5),$

insertIn$2()($insertIn$2/5),$

Both have $5$ arguments:

The incoming list

$2$ lists which hold temporary lists that build the answers

$2$ lists which will hold the answers

Both predicates will have the same base case $($facts$)$ corresponding to when the list to split is empty. It is:

insertIn$1([],$R$1,$R$2,$R$1,$R$2).$

It means "When there are no items to split, the temporary lists R$1$ and R$2$ are also the answer lists."

Your job is to write the $2$ rules that build the temporary lists:

$\%\%$ YOUR insertIn$1$ RULE HERE

insertIn$1([],$R$1,$R$2,$R$1,$R$2).\%\%$ This is the base case

$\%\%$ YOUR insertIn$2$ RULE HERE

insertIn$2([],$R$1,$R$2,$R$1,$R$2).\%\%$ This is the base case

What are the remaining $2$ rules?

Hints:

Both should separate the list to split into a head and a tail $([$H$|$T$]).$

Both should build the a list a their respective position

insertIn$1/5$ should call insertIn$2/5$

insertIn$2/5$ should call insertIn$1/5$