# Divide and conquer algorithm to sort a list where each element is root(n) away from its sorted position

I'm stuck on a question and I just need a hint/point in the general direction (not asking for the answer)

The question asks for the details of a divide and conquer algorithm that given a list that is almost sorted, runs in time $O(n)$.

What they mean by almost sorted is that given the list $x_1, x_2, \ldots, x_n$, if the sorted list is represented by $y_1, y_2, \ldots, y_n$ and for all $i, j \le n, x_i = y_j: |i-j| \le \sqrt n$.

The only thing that comes to mind is dividing the lists into $\sqrt n$ groups at each level (which would cause them to be at most length $\sqrt n$ for the first split), but I'm not too sure where to go from there. You'd have to join up $\sqrt n$ elements at a time as you recurse back up

I've also figured out that the recurrence would be: $T(n) = \sqrt{n} \cdot T(\sqrt n) + d \sqrt n$ which by the master's theorem is $O(n)$ time. So it kind of seems like I'm on the right track with the splitting, I'm just not sure if it should be split up a special way or compared a certain way or what.

You can't do it. Suppose you have $\sqrt{n}$ lists to sort, each $\sqrt{n}$ long, and consisting of integers between $1$ and $x_\mathrm{max}$. Create one list by adding $ix_\mathrm{max}$ to each member of the $i$th list and then concatenating them. Now, if you could sort this one list in $O(n)$ time, you would have sorted all of the $\sqrt{n}$ lists. But each one of these lists was arbitrary, and so each list requires $\sqrt{n} \;\log_2 \sqrt{n}$ steps, and the total number of steps required is $\frac{1}{2} n\; \log_2 n$.
• No, Peter's answer shows that there are $(\sqrt{n})!^{\sqrt{n}}$ different orders compatible with the assumptions of the problem, so we need $\log_2\left((\sqrt{n})!^{\sqrt{n}}\right)=\frac{1}{2}n\log_2 n-O(n)$ comparisons to sort, by the standard comparison tree lower bound argument. Whether you sort them independently or together makes no difference. – David Eppstein Feb 29 '12 at 0:19
• Your suggested lists can be sort in $O(\sqrt{n})$ by counting sort. I think is better to change your ranges. – Saeed Feb 29 '12 at 10:38
• It would be safer to write either "You can't do it with only comparisons" or "You can only do it if and only if you can sort any $n$ integers in $O(n)$ time." It is an open question whether an array of $n$ integers (one word each) can be sorted in $O(n)$ time on a $w$-bit integer RAM for all values of $w$. If $w$ is small enough, radix sort runs in $O(n)$ time; if $w$ is large enough, there are randomized linear-time sorting algorithms. – Jeffε Feb 29 '12 at 14:48