# How to sort using $\texttt{SQRTSORT}$ as a subroutine which sorts $\sqrt{n}$ of consecutive elements?

I am teaching myself algorithms with the online lecture notes by Jeff Erickson and fails to solve the following problem (Problem 21 of Lecture 1).

(a) Describe an algorithm that sorts an input array $A[1 \ldots n]$ by calling a subroutine $\texttt{SQRTSORT}(k)$, which sorts the subarray $A[k + 1 \ldots k + \sqrt{n}]$ in place, given an arbitrary integer $k$ between $0$ and $n - \sqrt{n}$. How many times does your algorithm call $\texttt{SQRTSORT}$ in the worst case?

Note: 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 $\texttt{SQRTSORT}$; in particular, your algorithm must not directly compare, move, or copy array elements.

(b) Prove that your algorithm from part (a) is optimal up to constant factors. In other words, if $f(n)$ is the number of times your algorithm calls $\texttt{SQRTSORT}$, prove that no algorithm can sort using $o(f(n))$ calls to $\texttt{SQRTSORT}$.

and,

(c) Now suppose $\texttt{SQRTSORT}$ is implemented recursively, by calling your sorting algorithm from part (a). For example, at the second level of recursion, the algorithm is sorting arrays roughly of size $n^{\frac{1}{4}}$. What is the worst-case running time of the resulting sorting algorithm?

Note: To simplify the analysis, assume that the array size $n$ has the form $2^{2^{k}}$, so that repeated square roots are always integers.

My Attempt:

For part (a), I come up with a probably brute-force algorithm behaving like the $\texttt{BubbleSort}$, except that it treats $\frac{\sqrt{n}}{2}$ of consecutive elements as a single one in $\texttt{BubbleSort}$. The number of calls of $\texttt{SQRTSORT}$ is at worst:

$$1 + 2 + \ldots + 2 \sqrt{n} = 2n + \sqrt{n} = \Theta(n)$$

For part (b), $\sqrt{n}$ is a trivial lower bound: Any reasonable algorithm must have done something on each element, consuming $\sqrt{n}$ calls of $\texttt{SQRTSORT}$.

My Questions:

1. How to show whether my solution is asymptotically optimal or not?
2. Do you have better algorithms with lower complexity, say, $\sqrt{n} \lg n$ or $n^{\frac{3}{4}}$. Actually, I am looking for the optimal one.
• Here's a puzzle that might be related, which you might enjoy: Suppose I give you a subroutine that will sort any list of size $m$ in place. How quickly can you sort a list of size $2m$, by repeatedly calling the subroutine? How many invocations of the subroutine are necessary? (It's possible to do it with $O(1)$ invocations of the subroutine.) – D.W. Aug 3 '14 at 6:08
• @D.W. It is possible to sort the list of size $2m$ by calling your subroutine 6 times, using the $\texttt{BubbleSort}$-like algorithm. How many invocations of the subroutine are necessary?: It is asking for the lower bound. I am not able to figure it out right now. However, consider the problem of sorting $2m = 4$ by comparison of any two ($m=2$) elements. It needs 5 comparisons at least. Back to my origin question, the size of the array to sort is $n = \sqrt{n} \times \sqrt{n}$ in which $\sqrt{n}$ is not a constant. I am stuck with this. – hengxin Aug 3 '14 at 7:25

Hint for part (b): Consider the statistic $r(\pi) = \sum_i |i-\pi(i)|$. Running SQRTSORT can reduce $r(\pi)$ by at most $n$, while $r(n(n-1)\ldots1) = \Omega(n^2)$.
Hint for part (c): I get a running time of $O(n^2\log^{O(1)} n)$.
• For part (c): I get $T(n) = n T(n^{1/2})$ which is $T(n) = \Theta(n^2)$. Could you please explain your method? – hengxin Sep 28 '14 at 9:40
• Sorry, corrected. You are missing a logarithmic term since it's really $T(n) = cnT(n^{1/2})$. – Yuval Filmus Sep 28 '14 at 9:41
• How does the constant $c$ become the logarithmic term $\log n$? – hengxin Sep 28 '14 at 9:45