For this problem, you have an array A[0], A[1], ..., A[n-1] of numbers (integers or floating point) to be sorted, where n is the length of the array. The array has already been partially pre-sorted in the following way: every t consecutive elements are already sorted, i.e., the following subarrays are sorted:

(A[0], A[1], ..., A[t-1])

(A[t], A[t+1], ..., A[2t-1])

(A[2t], A[2t+1],..., A[3t-1])

etc

The following is an example of array of values assuming t = 4:

3, 7, 13, 15, 0, 4, 9, 11, 5, 6, 10, 14, 1, 2, 8, 12

Assume that t divides n; and that t is known, i.e., its an input parameter. Also assume that t may grow with n, e.g., t may be approximately log n or the square root of n.

(a) Write down the pseudocode for an algorithm that sorts such an array. The input to the algorithm is the array A[ ], the length n, and parameter t. Analyze its running time and explain your analysis. For full credit, its time complexity must be the best asymptotic running time possible.

(Hint: Modify a sorting algorithm that you already know.)

(b) Prove a lower bound for sorting such a presorted array using a comparison-based sorting algorithm. It should match the running time of the algorithm in part (a). You must explain how you derived your lower bound.