Question

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[] 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 first time the merge method is executed as a result of the code segment above?

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 to form  {1, 4, 5, 9}.

D. {1, 3, 9} and  {5} are merged to form  {1, 3, 5, 9}.

E. {1, 3, 9} and  {4, 5} are merged to form  {1, 3, 4, 5, 9}.

Answer 1

The correct answer is:

A. {9} and  {1} are merged to form  {1, 9}.

Explanation:

The array is splitted into subarrays as:

({9}, {1}), ({3}, {5}) and {{4})

Hence, first 9 and 1 are merged to form {1, 9}