3. (35pts) In this question, we explain why quick sort is faster than merge sort in usual cases. We saw that the running time recurrence of merge sort is T(n)-2T + n The rightmost term n comes from merging two sorted arrays of n/2 elements. This is done in O(n) time but not too efficiently: We need to save the merged sequence in another array, and copy it back to Al1 to n] before returning A as the output. Considering this, we express the running time of merge sort by (C) T(n) -n, where b1>0 is a not too small constant. Merge sort always split A into halves to perform the merge operation, so (I) describes the average case behavior also. The average case running time recurrence of quick sort is (II) T(n) s- (T(k) +T(n - k -1) + bzn) k-0 Here the last summand is changed into b2n from n-1 given in class: n-1 came from comparing the pivoting element x with every other element in A and moving in A, so it is done quicker than the merge operation of merge sort. The required time is at most b2n for some constant b2 > 0 smaller than b Answer the three questions regarding (1) and (lI) a) Show that (I) means T(n) s c1n ln n for some c1 > 0 and all n 2 10. The number c1 must be minimum, expressed in terms of b (You can just assume the base case: T(n) cin logn is true if n0 and all n 2 10. The number c2 must be minimum, expressed in terms of b2. (You can just assume the base case: T(n)s c2n logn is true if n 3b2 d) With the above results, argue why quick sort is faster in practice in usual cases