2. Sorting. Consider the following algorithm for sorting a list of n numbers. If n 2 sort the numbers trivially. Otherwise, (i) recursively sort the first linl numbers in the list; then (ii) recursively sort the last numbers in the list, then (iii) recursively sort the first nl numbers in the list again. For example, if we want to sort 14,9.5,1,8.3) then we (G) recursively sort the first 4 numbers. This gives us (1,4,5,9,8,3). We then (ii) recursively sort, the last 4 numbers to get f1,4,3,5,8,9j. Finally we (ii) recursively sort the first 4 numbers to get (1,3,4,5,8,9 (a) Prove this sorting algorithm always works (b) Find the runming tine of this sorting algorithm by fornmlating and solving a recurrence relation for T'(n)