2. (20 pts, standard) As we all know, mergesort is a procedure that can sort an array of n integers in time O(n log n) in best-, average-, worst- cases. We also know that partition is a procedure, an array of n integers and splits the reorganized array into a low-part and a high-part, separated by the element indexed by r. Let mixsort(A, 1, n) be with return value r, that reorganizes an algorithm that sorts an array A with n integers. It works as follows: mixsort(A, 1, n) if n == 1, return, partition (A, l , n); //run insertsort on the low part insertsort(A, 1,T1) //run mergesort sort on the high part mergesort (A, +1,n); Compute the average-case time complexity of mixsort. Please faithfully fol- low the procedure of " write a formula" and "directly compute the solution". Please also show your math work