Near-Sort quicksort algorithm faster than O(nlgn)
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.