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

Problem Detail: 

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.

Asked By : hengxin

Answered By : Yuval Filmus

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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28886