Suppose that, instead of sorting an array, we just require that the elements increase on average. More precisely, we call an n-element array A k-sorted if, for all i = 1, 2, . . . ,n ? k, the following holds:

a. What does it mean for an array to be 1-sorted?

b. Give a permutation of the numbers 1, 2, . . . ,10 that is 2-sorted, but not sorted.

c. Prove that an n-element array is k-sorted if and only if A[i] ? A[i + k] for all i = 1, 2, . . . ,n ? k.

d. Give an algorithm that k-sorts an n-element array in O(n lg(n/k)) time. We can also show a lower bound on the time to produce a k-sorted array, when k is a constant.

e. Show that we can sort a k-sorted array of length n in O(n lg k) time.?

f. Show that when k is a constant, k-sorting an n-element array requires ?(n lg n) time.

ni+k-1 j=i A[j]_ C ni+k A[j] j=i+1 k k