Please help with this JAVA program

In this programming project you will practice the implementation of D&C algorithms. attached base codes for a starting place; they include some very simple testing code. You may modify the base le with your answers for all three questions. However, please retain the signatures of the two stub methods and make sure you keep all of your code in the base le.

Also attached is Sorting.java, which includes the textbook's sorting algorithm implementations for reference. The LinearNode, ListQueue, and Queue classes should not be modied.

~Merging sorted queues. Develop a static method that takes two queues of sorted items as arguments and returns a queue that results from merging the queues into sorted order. Emptying the input queues is ne. If you need to make any assumptions about the typing of the contents of the queues, please state them in a comment.

~Reimplement the mergesort algorithm to pass only arrays as parameters. The starting point will be the method public static void sort(Comparable[] a), which will start the recursive mergesort process. Plan to include a recursive helper method, public static Comparable[] mergesort(Comparable[] a), and a merge method, public static Comparable[] merge(Comparable[] a, Comparable[] b). Do not use global or class variables. (Note that this approach is slower than the mergesort from the book. The goal is to better understand the mergesort concept.)

~Implement a method, public static void shue(Object[] a), that shues an array in nlog(n) time using a recursive merging mechanism. Assume calls to the Random library happen in constant time. It should be possible for any element to re-position to any other position. Include a comment explaining why your algorithm runs in nlogn time.

Please see codes Provided below

public class BaseMerging {

/**

* Entry point for sample output.

*

* @param args the command line arguments

*/

public static void main(String[] args) {

Queue q1 = new ListQueue(); q1.enqueue("T"); q1.enqueue("R");

q1.enqueue("O"); q1.enqueue("L"); q1.enqueue("E");

Queue q2 = new ListQueue(); q2.enqueue("X"); q2.enqueue("S");

q2.enqueue("P"); q2.enqueue("M"); q2.enqueue("E"); q2.enqueue("A");

Queue q3 = new ListQueue(); q3.enqueue(20); q3.enqueue(17);

q3.enqueue(15); q3.enqueue(12); q3.enqueue(5);

Queue q4 = new ListQueue(); q4.enqueue(18); q4.enqueue(16);

q4.enqueue(13); q4.enqueue(12); q4.enqueue(4); q4.enqueue(1);

//Q1 - sample test cases

Queue merged1 = mergeQueues(q1, q2);

System.out.println(merged1.toString());

Queue merged2 = mergeQueues(q3, q4);

System.out.println(merged2.toString());

//Q2 - sample test cases

String[] a = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L",

"E"};

sort(a);

assert isSorted(a);

show(a);

//Q3 - sample test cases

String[] b = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L",

"E"};

shuffle(b);

show(b);

shuffle(b);

show(b);

}

public static Queue mergeQueues(Queue q1,

Queue q2) {

//TODO: implement this.

return new ListQueue();

}

public static void sort(Comparable[] a) {

//TODO: implement this.

}

public static void shuffle(Object[] a) {

//TODO: implement this.

}

//sorting helper from text

private static boolean less(Comparable v, Comparable w) {

return v.compareTo(w) < 0;

}

//sorting helper from text

private static void show(Comparable[] a) {

for (Comparable a1 : a)

System.out.print(a1 + " ");

System.out.println();

}

//sorting helper from text

public static boolean isSorted(Comparable[] a) {

for (int i = 1; i < a.length; i++)

if (less(a[i], a[i-1]))

return false;

return true;

}

}

LISTQUEUE

public class ListQueue implements Queue {

LinearNode tail; //back

LinearNode head; //front

private int count;

public ListQueue() {

tail = null;

count = 0;

}

@Override

public boolean isEmpty() {

return count == 0;

}

@Override

public void enqueue(Item item) {

LinearNode newNode = new LinearNode(item);

if(isEmpty())

head = newNode;

else

tail.setNext(newNode);

tail = newNode;

count++;

}

@Override

public Item dequeue() {

if(isEmpty())

throw new NoSuchElementException();

Item result = head.getElement();

head = head.getNext();

count--;

if(isEmpty())

tail = null;

return result;

}

@Override

public Item front() {

if(isEmpty())

throw new NoSuchElementException();

return head.getElement();

}

@Override

public String toString()

{

LinearNode iter = head;

String result = "";

while(iter != null) {

result = iter.getElement() + " " + result;

iter = iter.getNext();

}

return result + "(front)";

}

@Override

public int size() {

return count;

}

}

QUEUE.JAVA

public interface Queue {

/**

* Add an item.

* @param item an item

*/

public void enqueue(Item item);

/**

* Remove the least recently added item.

* @return an item

*/

public Item dequeue() throws NoSuchElementException;

/**

* Return, but do not remove, the most least added item.

* @return an item

*/

public Item front() throws NoSuchElementException;

/**

* Is the queue empty?

* @return if empty

*/

public boolean isEmpty();

/**

* Number of items in the queue.

* @return number of items

*/

public int size();

}

LINEARNODE.JAVA

public LinearNode(Item elem) {

next = null;

element = elem;

}

/**

* Returns the node that follows this one.

* @return reference to next node

*/

public LinearNode getNext() {

return next;

}

/**

* Sets the node that follows this one.

* @param node node to follow this one

*/

public void setNext(LinearNode node) {

next = node;

}

/**

* Returns the element stored in this node.

* @return element stored at the node

*/

public Item getElement() {

return element;

}

/**

* Sets the element stored in this node.

* @param elem element to be stored at this node

*/

public void setElement(Item elem) {

element = elem;

}

}