1. (10 pts) A grad student comes up with the following algorithm to sort an array A[1.n] that works by first sorting the first 2/3rds of the array, then sorting the last 2/3rds of the (resulting) array, and finally sorting the first 2/3rds of the new array. 1: function G-SORT(A, n) takes as input an array of n numbers, Al..n G-sort-recurse(A, 1, n) 3: end function function G-SORT-RECURSE(A, I, u) 4: 5: ifu_K0then D1 or fewer elements already sorted 2 elements D swap values return 7: else if uL 1 then temp Alu All temp end if 12: 13: 14: 15: 16: 17: 18: 19: 20: end functiorn else D 3 or more elements size u-1+1 twothirds- [(2 * size)/3] G-sort-recurse(A,L, l + twothirds - 1) G-sort-recurse(A, u twothirds +1,u) G-sort-recurse(A,e,e + twothirds - 1) end if First (5 pts), prove that the algorithm correctly sorts the numbers in the array (in increasing order) After showing that it correctly sorts 1 and 2 element intervals, you may make the (incorrect) assump- tion that the number of elements being passed to G-sort-recurse is always a multiple of 3 to simplify the notation (and drop the floors/ceilings). Next (1 pts), Derive a recurrence for the algorithm's running time (or number of comparisons made). Finally (4 pts), obtain a good asymptotic upper bound (big-O) for your recurrence. 1. (10 pts) A grad student comes up with the following algorithm to sort an array A[1.n] that works by first sorting the first 2/3rds of the array, then sorting the last 2/3rds of the (resulting) array, and finally sorting the first 2/3rds of the new array. 1: function G-SORT(A, n) takes as input an array of n numbers, Al..n G-sort-recurse(A, 1, n) 3: end function function G-SORT-RECURSE(A, I, u) 4: 5: ifu_K0then D1 or fewer elements already sorted 2 elements D swap values return 7: else if uL 1 then temp Alu All temp end if 12: 13: 14: 15: 16: 17: 18: 19: 20: end functiorn else D 3 or more elements size u-1+1 twothirds- [(2 * size)/3] G-sort-recurse(A,L, l + twothirds - 1) G-sort-recurse(A, u twothirds +1,u) G-sort-recurse(A,e,e + twothirds - 1) end if First (5 pts), prove that the algorithm correctly sorts the numbers in the array (in increasing order) After showing that it correctly sorts 1 and 2 element intervals, you may make the (incorrect) assump- tion that the number of elements being passed to G-sort-recurse is always a multiple of 3 to simplify the notation (and drop the floors/ceilings). Next (1 pts), Derive a recurrence for the algorithm's running time (or number of comparisons made). Finally (4 pts), obtain a good asymptotic upper bound (big-O) for your recurrence