(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 3. 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) - 2T+n, where b1>0 is a no 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