1. 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 A[1], etc.). Suppose we use, as our measure of time, the number of times we store a value into the array. In other words,

If x is any value, an assignment statement of the form A[i] = x has a cost of 1.

In particular, an assignment statement of the form A[i] = A[j ] has a cost of 1.

Any other operation (including a comparison between two array items A[i] and A[j ], 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 satis?es the cost and space requirements.

(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 satis?es the cost requirement and is in-place.