Suppose there is an efficient sorting algorithm called QuickSort2. QuickSort2 is similar to QuickSort except it is based on selecting 2 pivot elements 1 and 2 to divide the array into 3 parts. Assuming 1 < 2,

a) Derive the recurrence equation T(n)

b) Identify the worst-case scenario and the best-case scenario. You must justify your answer.

c) Using an analysis like the one we followed for QuickSort, derive a compact expression for the expected value of T(n), i.e., (())