Problem Seven (Total 18 points, 3 points for first 5 sub-problems; 6 points for number five) Answer the questions based on books merge sort algorithm

1. What is the running time of merger?
2. What is the running time of merger sort?
3. How many times the merger algorithm will be executed in a merger sort?
4. How many comparisons are needed to sort a list of 2048 elements?
5. Given array 8, 5, 3, 7, 1, 6, 4, 2. List array to show the array changes in memory. You may list out array after each merge call is terminated.

Problem Eight (7 points) According to your book, To partition the input, quicksort chooses a pivot to divide the data into low and high parts. The pivot can be any value within the array being sorted, commonly the value of the middle array element. Now rewrite the partition algorithm by using the last element of the subarray as the pivot.

Problem Nine (7 points) Write java code for any one of the two algorithms in Problem Five.