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