Please assist with this JAVA program. Thank you!

In this programming project you will practice the implementation of D&C algorithms. Download the attached base les 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 modi ed. (Sedgewick and Wayne: 2.2.14) 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 shu e(Object[] a), that shu es 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.

1 Sample Output Note that your shu e algorithm will return a di erent result than what is shown above since it relies on random numbers.

/** * Implements various merge style algorithms. * * Completion time: (your completion time) * * @author (your name), Acuna, Sedgewick and Wayne * @verison (version) */ 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; } }