I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or solution would be appreciated.
Describe an algorithm that sorts an input array $A[1..n]$ by calling a subroutine SQRTSORT(k), which sorts the subarray $A[k+1..k+\sqrt{n}]$ in place, given an arbitrary integer $k$ between $0$ and $n-\sqrt{n}$ as input. (To simplify the problem, assume that $\sqrt{n}$ is an integer.) Your algorithm is only allowed to inspect or modify the input array by calling SQRTSORT; in particular, your algorithm must not directly compare, move, or copy array elements. How many times does your algorithm call SQRTSORT in the worst case?
You can detect $l$ greatest values (and collect them in positions $n-l+1,\ldots,n$) from the array by calling SQRTSORT with $k=0$, $k=\sqrt{n}-l$, $k=2\sqrt{n}-2l$, and so on. Therefore, $2\sqrt{n}$ calls are sufficient to find $\sqrt{n}/2$ greatest values from array. Doing this recursively, we sort the array with at most $4n$ calls of SQRTSORT.
A lower bound better than $O(n)$ can not be expected, because some arrays require $cn^2$ transpositions of neighboring entries to be sorted. Note that SQRTSORT acts on $\sqrt{n}$ consequtive entries, and so a permutation caused by SQRTSORT call can be written as a composition of at most $O(n)$ transpositions of neighboring entries.