(c) Describe an in-place sorting algorithm that is optimal with respect to this cost model. That is, the time used by your algorithm should exactly match the lower bound given in (a).) Explain why your algorithm satisfies the cost requirement and is in-place.

2. Suppose we are given n numbers, initially stored in an array A and we wish to sort them. When the sort concludes, the sorted output is to be in the array A, in ascending order (i.e., the smallest value in A[0], the next smallest in A1], etc.). Suppose we use, as our measure of time, the number of times we store a value into the array. In other words, . If is any value, an assignment statement of the form Ali] has a cost of 1. In particular, an assignment statement of the form AlAj has a cost of 1 Any other operation (including a comparison between two array items Al] and ALi], or an assignment x = A[i] where x is not a location in the array A) has a cost of 0. (a) Under this cost model, give a lower bound on the worst-case time required to sort the array A. Your answer should be an exact expression in terms of n (i.e., it should not involve asymptotic notation). (b) Describe a sorting algorithm that is optimal with respect to this cost model and uses O(n) space. That is, time used by your algorithm should exactly match the lower bound given in (a).) Explain why your algorithm satisfies the cost and space requirements