1) Problems 4.6 (6 points), 7.15 (6 points)
2) Using Binary Search, find the index of 37 in the following array (the first index is 0). Show the values of left and right
at the begining of each recursive call. (6 points)
(1,2,3,5,7,9,11,12,12,12,34,35,36,37,42,42,42,42,111,111,111,99999)
3) Using the Mergesort algorithm given on the slides, sort the following array. (6 points)
(12, 2, 1, 7, 20, 99, 4, 14)
Show the state of the array at the beginning and end of each call to mergesortRec(), except for those
calls that immediately return. Also give
the values of the arguments left and right at the beginning of each call.
Hint: you can safely ignore the implementation details of merge() as long as you are aware
what the result of merge() is.