Java coding

/** Merge contents of arrays S1 and S2 into properly sized array S. */

public static <K> void merge(K[] S1, K[] S2, K[] S, Comparator<K> comp) {

int i = 0, j = 0;

while (i + j < S.length) {

if (j == S2.length || (i < S1.length && comp.compare(S1[i], S2[j]) < 0))

S[i+j] = S1[i++]; // copy ith element of S1 and increment i

else

S[i+j] = S2[j++]; // copy jth element of S2 and increment j

}

}

/** Merge-sort contents of array S. */

public static <K> void mergeSort(K[] S, Comparator<K> comp) {

int n = S.length;

if (n < 2) return; // array is trivially sorted

// divide

int mid = n/2;

K[] S1 = Arrays.copyOfRange(S, 0, mid); // copy of first half

K[] S2 = Arrays.copyOfRange(S, mid, n); // copy of second half

// conquer (with recursion)

mergeSort(S1, comp); // sort copy of first half

mergeSort(S2, comp); // sort copy of second half

// merge results

merge(S1, S2, S, comp); // merge sorted halves back into original

}

2. With the partial implementation of the “Quick-Sort” algorithm (shown below, so-called divide and conquer areas), build a test program that sorts an unsorted array of the size of 20. Again, you may need Queue, LinkedQueue or any other classes and interfaces to import.

/** Quick-sort contents of a queue. */

public static <K> void quickSort(Queue<K> S, Comparator<K> comp) {

int n = S.size();

if (n < 2) return; // queue is trivially sorted

// divide

K pivot = S.first(); // using first as arbitrary pivot

Queue<K> L = new LinkedQueue<>();

Queue<K> E = new LinkedQueue<>();

Queue<K> G = new LinkedQueue<>();

while (!S.isEmpty()) { // divide original into L, E, and G

K element = S.dequeue();

int c = comp.compare(element, pivot);

if (c < 0) // element is less than pivot

L.enqueue(element);

else if (c == 0) // element is equal to pivot

E.enqueue(element);

else // element is greater than pivot

G.enqueue(element);

}

// conquer

quickSort(L, comp); // sort elements less than pivot

quickSort(G, comp); // sort elements greater than pivot

// concatenate results

while (!L.isEmpty())

S.enqueue(L.dequeue());

while (!E.isEmpty())

S.enqueue(E.dequeue());

while (!G.isEmpty())

S.enqueue(G.dequeue());

}

Please send me the source code you designed and the answer (55 points).