Consider the following mergeSortHelper method, which is part ofan algorithm to recursively sort an array of integers.
/** Precondition: (arr.length == 0 or 0 <= from<= to <= arr.length)
* arr.length == temp.length
*/
public static void mergeSortHelper(int[] arr, int from, int to,int[] temp)
{
if (from < to)
{
int middle = (from + to) / 2;
mergeSortHelper(arr, from, middle, temp);
mergeSortHelper(arr, middle + 1, to, temp);
merge(arr, from, middle, to, temp);
}
}
The merge method is used to merge two halves of anarray (arr[from] througharr[middle], inclusive, and arr[middle + 1]through arr[to], inclusive) when each half hasalready been sorted into ascending order. For example, consider thearray arr1, which contains the values {1, 3, 5, 7,2, 4, 6, 8}. The lower half of arr1 is sorted inascending order (elements arr1[0] througharr1[3], or {1, 3, 5, 7}), as isthe upper half of arr1 (elements arr1[4] througharr1[7], or {2, 4, 6, 8}). Thearray will contain the values {1, 2, 3, 4, 5, 6, 7, 8} after themethod call merge(arr1, 0, 3, 7, temp). The arraytemp is a temporary array declared in the calling program.
Consider the following code segment, which appears in a methodin the same class as mergeSortHelper and merge.
int[] arr1 = {9, 1, 3, 5, 4};
int[] temp = new int[arr1.length];
mergeSortHelper(arr1, 0, arr1.length - 1, temp);
Which of the following represents the arrays merged the firsttime the merge method is executed as a result of the code segmentabove?
A. {9} and {1} are merged to form {1,9}.
B. {1, 9} and {3} are merged to form {1,3, 9}.
C. {1, 9} and {5, 4} are merged toform {1, 4, 5, 9}.
D. {1, 3, 9} and {5} are merged toform {1, 3, 5, 9}.
E. {1, 3, 9} and {4, 5} are merged toform {1, 3, 4, 5, 9}.
