Consider the following mergeSortHelper method, which is part of an 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 an array (arr[from] through arr[middle], inclusive, and arr[middle + 1] through arr[to], inclusive) when each half has already been sorted into ascending order. For example, consider the array arr1, which contains the values {1, 3, 5, 7, 2, 4, 6, 8}. The lower half of arr1 is sorted in ascending order (elements arr1[0] through arr1[3], or {1, 3, 5, 7}), as is the upper half of arr1 (elements arr1[4] through arr1[7], or {2, 4, 6, 8}). The array will contain the values {1, 2, 3, 4, 5, 6, 7, 8} after the method call merge(arr1, 0, 3, 7, temp). The array temp is a temporary array declared in the calling program.
Consider the following code segment, which appears in a method in the same class as mergeSortHelper and merge.
int[] vals = {80, 50, 30, 20, 60, 70};
int[] temp = new int[vals.length];
mergeSortHelper(vals, 0, vals.length - 1, temp);
Which of the following represents the arrays merged the last time the merge method is executed as a result of the code segment above?
A
{20, 30, 50} and {60, 70, 80} are merged to form {20, 30, 50, 60, 70, 80}.
B
{20, 50, 70} and {30, 60, 80} are merged to form {20, 30, 50, 60, 70, 80}.
C
{20, 50, 70} and {30, 60, 80} are merged to form {20, 50, 70, 30, 60, 80}.
D
{30, 50, 80} and {20, 60, 70} are merged to form {20, 30, 50, 60, 70, 80}.
E
{30, 50, 80} and {20, 60, 70} are merged to form {30, 50, 80, 20, 60, 70}.
D
{30, 50, 80} and {20, 60, 70} are merged to form {20, 30, 50, 60, 70, 80}.