Implement a recursive merge-sort algorithm using the array-based implementation. Include a main method that runs

sorting on the hardcoded sequence of integers.

Use the code below to get an idea of array based implementation. Please don't post an answer unless you can fully answer the question and the code must compile and run.

public class Merge

{

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

public static void merge(K[ ] S1, K[ ] S2, K[ ] S, Comparator 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 void mergeSort(K[ ] S, Comparator 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

}

}