# Complexity of sorting $k$-sorted array using QuickSort and HeapSort

Given a $$k$$-sorted array where each element in the array is $$k$$ positions from its correct position, we want to sort such array using quick sort. Generally speaking, I understand that running time is very unlikely to be guaranteed for best case and thus in most cases you would end up with $$O(n^2)$$ running time though quicksort runs in $$O(n\log{n})$$ in best case/average case scenario.

# QuickSort

Best case: I am looking to proof why we get $$O(n^2)$$ even in average case. If we rewrite the quick sort recurrence as,

$$T(n) = T(k) + T(n-k) + O(n) \tag{1}\label{1}$$

We can see that the depth of the recurrence tree is $$\frac nk$$, thus $$T(n) = O(n^2)$$.

Worst Case: It's $$T(n)=T(1)+T(n-1)$$ is clear.

Problem 1: how do you interpret please \ref{1} given k-sorted array definition?

Problem 2: from \ref{1} I see that the recurrence of quicksort is written by taking each element that is $$k$$ positions from its correct place in the sorted array as a pivot if I am were right please? So, we split it into two subproblems of size $$k$$ and $$n-k$$. However, the resulting elements in the subproblems might have less than $$k$$ distance from their positions due to divisions of problem into sub problems, so I am just a little bit confused as whether the property that each element is $$k$$ position from its correct place is invariant or not given we are splitting the array into sub problems.

Problem 3: why please the depth of recurrence tree after we do quick sort is $$\frac nk$$? My interpretation to this does not apply here as I was thinking that the depth of the node represents how far it's from correct position, but still not sure about it.

# HeapSort

Let us discuss HeapSort approach and why it's more efficient that QuickSort.

if we use heap sort instead of quicksort and we then take $$k+1$$ elements and add them in a heap that is sorted (min heap), so once we have $$k+1$$ elements and we are about to visit $$k+2$$th element, we pop the min element from heap and add it to the array that will hold sorted elements. So, we can imagine the array as being literally divided into sublists. To formalize this, let $$A[i] < A[i+2k+1]$$.

Problem 4: I would like to discuss please $$A[i] < A[i+2k+1]$$. Approach 1: It's obvious that each element in the array can be less than at most $$n-(k)$$ elements or from all elements on the right and all elements on the left $$n-(k)$$ , so in total we need $$n-2k$$? Is this is how $$A[i] < A[i+2k+1]$$ was deduced above please? Approach 2: The solution I got says that, "because the element at slot $$i$$ can at most move forwards during sorting to slot $$i+k$$ and the element at slot $$i+2k+1$$ can at most move backwards during sorting to slot $$i+k+1$$." I am having troubles understanding this proposed solution anyway? So please either discuss it or discuss my approach (approach 1).

## 2 Answers

For quick sort, you end up with quadratic runtime only if you use the most stupid method of picking a pivot- by taking the first or last element. Picking the middle element, or the median of first, last and middle element, it will run nicely fast because for all except 2k elements we have just comparisons, and nothing will be moved. Still n log n, but with a small constant factor.

There is a slightly complicated variant of heap sort that works well for mostly sorted arrays, someone might know the name.

PS. In one instance where an array is almost sorted, bubble sort was recommended and worked very well. The situation was a large number of 2d lines, and their intersection with some y-value was needed in sorted order. After a small change in y, the intersections change slightly, so k was very small (less than log n usually) and bubble sort ran in k x n steps. Solution due to Paul Hsieh I think, hope he’s alive and well.

The analysis questioned in Problem 3 assumes(?) an implementation closer to ACM Algorithm 64 than to what Sedgewick is getting at (as does "Problem 1"): recursion on all partitions, not "iteration on the biggest one".