Suppose that, instead of sorting an array, we just require that the elements increase on average. More precisely, we call an -element array [1 ] -sorted if for all in the range 1 , the following holds:

Describe an algorithm that -sorts an -element array in time ( log ).

+k-1 +k *-1 A[j] [j] i=i- === k +k-1 +k *-1 A[j] [j] i=i- === k