QUESTION 1 Suppose Mergesort is run on the array 23546081 Which of the following will actually occur at some point during the execution of the algorithm? "Merge of x xxx and Y Y Y Y" means a merge operation is called on those two exact lists at some point.) Merge of 2 3 45 and 01 6 8. A comparison of the 2 and the 8 O Merge of O 1 and 6 8 Merge of 0 123 and4568 O Merge of 2 3 and 0 6. Comparison of the 2 and the S5. QUESTION 2 Which of the following best describes the state of the Mergesort algorithm just before the final merge? The recursion gets down to a single element, which is easy to sort The first N-1 elements of the array are sorted relative to each other, and only the final element is out of place. All the elements of the array are sorted except for two, which are swapped Two sorted arrays (possibly stored as two haves of a single array QUESTION 3 In Insertion Sort, which of the following best describes the state of the array just before the last element of the array is compared for the first time? (Don't pick an answer that is only true in special cases.) O The first N-1 elements of the array are sorted relative to each other, leaving only the final element potentially out of order O The array is sorted besides two out-of-order elements, which should be swapped. The array is actually sorted already, and just needs a final pass to check that this is the case. 0 The item that used to be at the end of the array is now one space away from where it should be