<p>You can't do it. Suppose you start with an array where everything is sorted to distance $k$. Then, you can use a modified QuickSort to sort this array in time $n \log k$. </p>

<blockquote>
  <p>First, choose pivot elements every $k$ elements. Now, sort the array so everything is in place with respect to these elements. (You can do this in time $O(n)$ using a modified version of Quicksort. First, put everything to the left of the first pivot element on the correct side of this pivot element. This takes $O(k)$ time. Next, put everything between the first and second pivot elements on the correct side of the second pivot element. Repeat for the rest of the pivot elements, from left to right.) Finally, sort each of the sublists between the pivot elements. </p>
</blockquote>

<p>This will take total time $O(n \log k)$. Now, if you could take an arbitrary array to a nearly-sorted array in time less than $o(n\log n - n \log k)$, we would sort in time $o(n \log n)$. We can't do this.</p>

<p>Thus, there is an $\Omega(n \log \frac{n}{k})$ time bound on near-sorting.  </p>

CC BY-SA 3.0
2012-11-26T22:34:54.860Z
Isn't MergeSort an `O(nlgn)` algorithm?
YoryeNathan
CC BY-SA 3.0
2012-11-26T22:35:57.587Z
@Yorye: this isn't MergeSort.
Peter Shor 
CC BY-SA 3.0
2012-11-26T22:39:21.717Z
@Yorye: Why do you believe it's possible?
Peter Shor 
CC BY-SA 3.0
2012-11-26T22:41:36.813Z
Yes, but QuickSort's avg. case is also `O(nlgn)`.
YoryeNathan
CC BY-SA 3.0
2012-11-26T22:42:51.757Z
@PeterShor Just the trust in my university to give us a valid exercise.
YoryeNathan
CC BY-SA 3.0
2012-11-26T22:43:39.713Z
In my highlighted algorithm above, we sort $n/k$ lists of size each at most $3k$. The total time required for this is $O(3k \log 3k \cdot n/k) = O(n \log k)$.
Peter Shor 
CC BY-SA 3.0
2012-11-26T22:46:33.313Z
@Yorye: Maybe you should read the assignment more carefully, or maybe you shouldn't trust them.
Peter Shor 
CC BY-SA 3.0
2012-11-26T22:54:32.847Z
The question seems related to CLRS Ex. 8.1-4.
Kaveh
CC BY-SA 3.0
2012-11-26T22:56:56.010Z
@PeterShor Yes, I also came up with that idea, but it reminded me too much of MergeSort, and I was asked for a "small tweak", not a different algorithm, so I assumed there might be something else. Or maybe I didn't understand your algorithm correctly?
YoryeNathan
CC BY-SA 3.0
2012-11-26T22:32:21.527Z
2012-11-26T22:37:26.477Z
2012-11-26T22:37:26.477Z
Peter Shor 
<p>Here, we define a nearly-sorted array with k-sized error, as this:
Elements in the array may be in the wrong order, but only if they are not distanced by more than k indices.
For example:</p>

<p>1, 2, 3, <strong>6</strong>, <strong>5</strong>, <strong>4</strong>, 7, 8, 9</p>

<p>The 6 and the 4 are in the wrong order, and they are 2 indices apart from one another.
The rest of the elements are in order, or of less than 2 indices apart.
So the above array is nearly-sorted with an error size 2.</p>

<hr>

<p><strong>The question is, how to "tweak" the simple and basic version of the QuickSort algorithm, to have it produce a nearly-sorted array instead of a fully-sorted array, given a certain k, and thereby making it faster than <code>O(nlgn)</code>?</strong></p>

<p>I've been thinking about this for days now, and I can't seem to understand how "ignoring" some of the elements while sorting, in any way, can ever change the run-time complexity of the algorithm, where k is constant?</p>

<p><em>I could easily just stop the recursion if <code>size &lt; k</code> instead of <code>size &lt; 2</code>, which would indeed make it faster by a tiny bit, and will indeed have possible errors, but wouldn't it still be <code>O(nlgn)</code>?</em></p>

<p><strong>Any help or direction will be appreciated!</strong></p>

CC BY-SA 3.0
2012-11-26T22:36:47.010Z
What is the motivation for your question? Is this an assignment?
Kaveh
CC BY-SA 3.0
2012-11-26T22:41:17.980Z
@Kaveh Yes, it is.
YoryeNathan
CC BY-SA 3.0
2012-11-26T22:42:34.900Z
cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Assignment questions are generally off-topic here.
Kaveh
<approximation-algorithms><time-complexity><sorting>
Near-Sort quicksort algorithm faster than O(nlgn)
YoryeNathan
# Near-Sort quicksort algorithm faster than O(nlgn)

(Asked by: username_0 on 2012-11-26)

Here, we define a nearly-sorted array with k-sized error, as this:
Elements in the array may be in the wrong order, but only if they are not distanced by more than k indices.
For example:

1, 2, 3, **6**, **5**, **4**, 7, 8, 9

The 6 and the 4 are in the wrong order, and they are 2 indices apart from one another.
The rest of the elements are in order, or of less than 2 indices apart.
So the above array is nearly-sorted with an error size 2.

---

**The question is, how to "tweak" the simple and basic version of the QuickSort algorithm, to have it produce a nearly-sorted array instead of a fully-sorted array, given a certain k, and thereby making it faster than `O(nlgn)`?**

I've been thinking about this for days now, and I can't seem to understand how "ignoring" some of the elements while sorting, in any way, can ever change the run-time complexity of the algorithm, where k is constant?

*I could easily just stop the recursion if `size < k` instead of `size < 2`, which would indeed make it faster by a tiny bit, and will indeed have possible errors, but wouldn't it still be `O(nlgn)`?*

**Any help or direction will be appreciated!**

**Tags:** approximation-algorithms, time-complexity, sorting
> **Comments:**
> **username_1**: What is the motivation for your question? Is this an assignment?  
> **username_0**: @Kaveh Yes, it is.  
> **username_1**: cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Assignment questions are generally off-topic here.  

---

## 1 answers

### Answer by username_2 on 2012-11-26. Score: 4

You can't do it. Suppose you start with an array where everything is sorted to distance $k$. Then, you can use a modified QuickSort to sort this array in time $n \log k$.

> First, choose pivot elements every $k$ elements. Now, sort the array so everything is in place with respect to these elements. (You can do this in time $O(n)$ using a modified version of Quicksort. First, put everything to the left of the first pivot element on the correct side of this pivot element. This takes $O(k)$ time. Next, put everything between the first and second pivot elements on the correct side of the second pivot element. Repeat for the rest of the pivot elements, from left to right.) Finally, sort each of the sublists between the pivot elements.

This will take total time $O(n \log k)$. Now, if you could take an arbitrary array to a nearly-sorted array in time less than $o(n\log n - n \log k)$, we would sort in time $o(n \log n)$. We can't do this.

Thus, there is an $\Omega(n \log \frac{n}{k})$ time bound on near-sorting.

> **Comments:**
> **username_0**: Isn't MergeSort an `O(nlgn)` algorithm?  
> **username_2**: @Yorye: this isn't MergeSort.  
> **username_2**: @Yorye: Why do you believe it's possible?  
> **username_0**: Yes, but QuickSort's avg. case is also `O(nlgn)`.  
> **username_0**: @PeterShor Just the trust in my university to give us a valid exercise.  
> **username_2**: In my highlighted algorithm above, we sort $n/k$ lists of size each at most $3k$. The total time required for this is $O(3k \log 3k \cdot n/k) = O(n \log k)$.  
> **username_2**: @Yorye: Maybe you should read the assignment more carefully, or maybe you shouldn't trust them.  
> **username_1**: The question seems related to CLRS Ex. 8.1-4.  
> **username_0**: @PeterShor Yes, I also came up with that idea, but it reminded me too much of MergeSort, and I was asked for a "small tweak", not a different algorithm, so I assumed there might be something else. Or maybe I didn't understand your algorithm correctly?  

---

