We can describe the Merge-Sort algorithm on an array of n elements, where n is a
ID: 3640732 • Letter: W
Question
We can describe the Merge-Sort algorithm on an array of n elements, where n is a power of 2 (i.e., 2, 4, 8, 16, 32, etc.), informally as follows:1. If n = 2, return a list of the two elements sorted, lowest first.
2. If n > 2, recursively Merge-Sort the left (low-index) half of the array, to produce a sorted list L1, and recursively sort the right (high-index) half of the array to produce a sorted list L2.
3. Merge L1 and L2 to produce a single sorted list.
Suppose we apply Merge-Sort to an array of length 16, whose elements have values:
12, 4, 10, 1, 14, 6, 3, 11, 7, 13, 2, 15, 8, 5, 16, 9
in order, from the left. Simulate Merge-Sort on this array. Which of the following lists will be L1 (not L2) in some call to Merge-Sort?
What does the following method do for the call printArray (a, a.length)
for the array a = { 54, 23 36 }?
What is wrong with this method? Fix the problem, if you can.
void printArray ( int[] values, int n )
{
if ( n < 0 )
return;
n--;
printArray ( values, n );
System.out.print (values[n] );
}
What is the fix?
Lori first coded recursive binarySearch() as follows. Where did she go wrong?
public static int binarySearch ( int[] coll, int target )
{
int first = 0,
last = target.length,
mid = (first + last ) / 2;
if ( first > last ) return -1; // failure — base case
if (coll [ mid ] == target ) // success — base case
return mid;
if (coll [ mid ] < target ) { // recursive cases
last = mid – 1;
return binarySearch ( coll, target );
}
else {
first = mid + 1;
return binarySearch ( coll, target );
}
}