2 Lower bound for sorting partially pre-sorted arrays (30 pts) Consider the following problem. You have an array A of size n that you would like to sort. However, someone was nice enough to sort parts of it for you already. In particular, every t consecutive elements are already (a) (15 pts) Write down the pseudocode for an algorithm that sorts such an array and analyze its running (b) (15 pts) Prove a lower bound for sorting such a presorted array using a comparison-based sorting sorted, i.e., the subarrays A[1..t], A[(t + 1)..2t], A[2t + 1)..3t], , A [(n-t + 1)..n] are already sorted. time. You will receive full credit if your algorithm exhibits the best asymptotic running time possible. algorithm. Does it match the running time of the algorithm in part (a)? Hint: Think about how many different permutations are possible in such an array