Lower bound on comparison-based sorting of $k$-sorted arrays

Question

In $k$-sorting array algorithms, every element is supposed to be $k$ positions from its correct positions. So with that in mind, if we used a randomized QuickSort, we will have $O(n\log{n})$. Now to prove a lower bound on this, we assume $k \le \frac n2$.

Question: Prove that you can not do better than $O(n\log n)$ on a $k$-sorted array.

Goal: I see here that the point is if we can prove that the lowest we can do is $\Omega(n\log n)$, then that would confirm that we can not do better than $O(n\log n)$ and that will finish the proof.

So, let us consider all possible permutations of $k$. Part of the solution reads:

Our goal is to prove a lower bound on the number of leaves in a decision tree for an algorithm that sorts an array in which every element is within $k$ positions of its proper position. We therefore provide a lower bound on the number of possible permutations that satisfy this condition.

Next, if we break the array into blocks of length $k$ (with a last block which is possibly smaller), each element will be at most $k$ positions from its correct place. For each full block there are $k!$ possible permutations, thus we have $(k!)^{\lfloor \frac nk \rfloor}$ total permutations of the entire array.

We can then prove a lower bound based on the number of leaves in the decision tree: the lower bound is the logarithm of the number of leaves, which is

$$\ge \log{(k!)^{\lfloor \frac nk \rfloor}} = \Omega(n\log k).$$

Problems:

1. Why for proving a lower bound, we assume $k \le \frac n2$ in the first place? Why this factor specifically was taken into consideration, and why this contributes to finding a lower bound for any algorithm that works for $k$-sorted arrays?
2. So, do we want to go over all permutations of $k$ so that we prove that for each permutation we can still do better than $O(n\log n)$, is this the goal? Is this why we want to consider all permutations based on $k$?
3. How does $\ge \log{(k!)^{\lfloor \frac nk \rfloor}}$ fit in the whole analysis? Why did we start from this? We want to prove a lower bound for $k$-sorted arrays, namely that no algorithm can do better than $O(n\log n)$, so we want a lower bound that does not exceed that, thus we take permutations, which in turn corresponds to leaves in the decision tree. Can you please rephrase the whole approach in your own words? No solution is needed.

Answer 1

The complexity of sorting a $k$-sorted array is actually $\Theta(n\log (k+1))$. Given a $k$-sorted array, you can use a modification of heapsort to sort it using only $O(n\log (k+1))$ comparisons. You put the first $2k$ elements in a heap, and you then repeatedly add the next element to the heap, and extract the minimum element from the heap. After exhausting the original array, you repeatedly extract the minimum element from the heap until it is empty. The extracted elements form the correctly sorted array.

The goal of your question is to provide a matching lower bound of $\Omega(n\log (k+1))$ on comparison-based sorting algorithms. This is not a lower bound only on quicksort; any comparison-based sorting algorithm must make at least $\Omega(n\log (k+1))$ comparisons in the worst-case. There is no need to assume that $k \leq n/2$ for this lower bound.

The idea of the proof is as follows. Suppose that there are $N_k$ many $k$-sorted arrays consisting of the numbers $1,\ldots,n$. You can describe any comparison-based algorithm as a decision tree. Each of the $N_k$ many arrays must end at a different leaf of the decision tree, and so the decision tree has height at least $\log_2 N_k$. Consequently, the number of comparisons in the worst case is at least $\log_2 N_k$.

Here is a construction of $(k!)^{\lfloor n/k \rfloor}$ many $k$-sorted arrays consisting of the numbers $1,\ldots,n$: the first $k$ elements are an arbitrary permutation of $1,\ldots,k$, the following $k$ elements are an arbitrary permutation of $k+1,\ldots,2k$, and so on. In fact, we can slightly improve this construction by replacing $k$ by $k+1$, obtaining $N_k \geq ((k+1)!)^{\lfloor n/(k+1) \rfloor}$. This gives a lower bound of $$ \log_2 ((k+1)!)^{\lfloor n/(k+1) \rfloor} = \lfloor n/(k+1) \rfloor \log_2 (k+1)! = \Omega(n/(k+1)) \cdot \Omega((k+1)\log(k+1)) = \Omega(n\log (k+1)). $$