Computer Science- Data Structure and Algorithms

Do code in Java. Please make sure properly formatted. Thanks

The arrays of varying lengths are in text file 50_text.input and 100_text.input. I can't upload the text files, so use sample text input.

// NOTE: You have to allocate temp array in the main method and copy the original input array A to // the temp array before invoking merge sort in the main method.

MERGE-SORT (A, temp, p , r) if p

q = |_ (p + r) / 2 _| MERGE-SORT (A, temp, p , q) MERGE-SORT (A, temp, q + 1, r) MERGE (A, temp, p, q, r)

//////////////////////////////////////////////

MERGE (A, temp, p, q, r) // merge A[p..q] with A[q+1..r] i=p j=q+1

// copy A[p..r] to temp[p..r] for k = p to r

temp[k] = A[k]

//merge back to A[p..r] for k = p to r

if i > q // left half empty, copy from the right A[k] = temp[j]

j=j+1 else if j > r // right half empty, copy from the left

A[k] = temp[i]

i=i+1 else if temp[j]

A[k] = temp[j]

j=j+1 else

A[k] = temp[i] i=i+1

// copy from the right

// copy from the left

Implement a method to sort a given array using the merge sort algorithm. Use the algorithm provided (see Page 2) instead of the algorithm from the textbook. Write a driver program to test the merge sort algorithm for arrays of varying lengths provided in Canvas