Consider the following idea for sorting a a list of size n: Split the list into lists of size each, sort each of the smaller list individually and then merge the sorted lists to get a single sorted list.

(a) Let T(n) denote the worst case running time of an algorithm based on this idea. Derive a recurrence relations for T(n) . Provide a clear explanation of how you arrived at his recurrence.

(b) Solve the recurrence relation to determine a function g(n) such that