<p>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$<sup>th</sup> 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$. </p>

CC BY-SA 3.0
2012-02-29T00:19:09.287Z
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
CC BY-SA 3.0
2012-02-29T10:38:00.497Z
Your suggested lists can be sort in $O(\sqrt{n})$ by counting sort. I think is better to change your ranges.
Saeed
CC BY-SA 3.0
2012-02-29T14:48:58.950Z
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ε
CC BY-SA 3.0
2012-02-28T21:31:22.657Z
2012-02-29T13:41:58.177Z
2012-02-29T13:41:58.177Z
Peter Shor 
<p>I'm stuck on a question and I just need a hint/point in the general direction (not asking for the answer)</p>

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

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

<p>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</p>

<p>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.</p>

<p>Thanks in advance</p>

CC BY-SA 3.0
2012-02-28T21:32:37.847Z
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?
Peter Shor 
CC BY-SA 3.0
2012-02-28T21:51:16.883Z
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)
user8575
<ds.algorithms>
Divide and conquer algorithm to sort a list where each element is root(n) away from its sorted position
user8575
# Divide and conquer algorithm to sort a list where each element is root(n) away from its sorted position

(Asked by: username_0 on 2012-02-28)

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

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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)  

---

## 1 answers

### Answer by username_1 on 2012-02-28. Score: 17

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

> **Comments:**
> **username_2**: 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.  
> **username_3**: Your suggested lists can be sort in $O(\sqrt{n})$ by counting sort. I think is better to change your ranges.  
> **username_4**: 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.  

---

