Answer Happy

1. Given the input array below, trace the Mergesort algorithm for sorting the array in descending order. Show the content of the array at the end of each recursive call to the algorithm. 4 10 9 3 14 5 11 1 8 13 6 7 2 12 5 7 2. Given the input array below, trace the Quicksort algorithm for sorting the array in descending order. Show the content of the array at the end of each recursive call to the algorithm. 4 10 9 3 14 5 11 1 8 13 6 7 2 12 3. Give an algorithm to rearrange an array of n keys so that all the negative keys precede all the nonnegative keys. Your algorithm must be in-place, meaning you cannot allocate another array to temporarily hold the items. Your algorithm must run in linear time (i.e. O(N)). You may only use constant size (i.e. O(1)) additional memory. First explain how your method works in 2-3 sentences, and then write Java code below. How fast is your algorithm? Hint: modify the partition function of the quicksort algorithm.