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.

Thanks in advance

  • 3
    $\begingroup$ We generally don't answer (or even give hints for) homework questions here, but I'm making an exception this time. Are you sure you gave us the problem correctly? $\endgroup$ – Peter Shor Feb 28 '12 at 21:32
  • $\begingroup$ this is it almost exactly: We are given a sequence of n distinct numbers to sort. The sequence is "close” to being sorted, in the sense that every element is within √n positions of where it is supposed to be. That is, we're given x1; x2; : : : ; xn; say that the correctly sorted list is y1; y2; : : : ; yn; then for all i; j if xi = yj , then |i − j| ≤ √n We have to show how to use a divide and conquer algorithm to sort this in time O(n) $\endgroup$ – user8575 Feb 28 '12 at 21:51

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

  • 11
    $\begingroup$ 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. $\endgroup$ – David Eppstein Feb 29 '12 at 0:19
  • $\begingroup$ Your suggested lists can be sort in $O(\sqrt{n})$ by counting sort. I think is better to change your ranges. $\endgroup$ – Saeed Feb 29 '12 at 10:38
  • 9
    $\begingroup$ 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. $\endgroup$ – Jeffε Feb 29 '12 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.