Near-Sort quicksort algorithm faster than O(nlgn) [closed]

Question

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!

Answer 1

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.