Lower bound for $k$-sorting an array

Question

This is exercise 2 of the lecture note by Jeff Erickson on decision tree lower bounds.

We say that an array $A[1 \ldots n]$ is $k$-sorted if it can be divided into $k$ blocks, each of size $n/k$ (we assume that $n/k$ is an integer), such that the elements in each block are larger than the elements in earlier blocks and smaller than elements in later blocks. The elements within each block need not be sorted.

(a) Describe an algorithm that $k$-sorts an arbitrary array in $O(n \log k)$ time.
(b) Prove that any comparison-based $k$-sorting algorithm requires $\Omega(n \log k)$ comparisons in the worst case.
(c) Describe an algorithm that completely sorts an already $k$-sorted array in $O(n \log(n/k))$ time.
(d) Prove that any comparison-based algorithm to completely sort a $k$-sorted array requires $\Omega(n \log(n/k))$ comparisons in the worst case.

---

The first problem can be solved by modifying the quicksort algorithm. However, I am stuck with the second problem which asks for a lower bound. My attempt is to use the decision tree technique. I think the number of leaves of the decision tree is at least $((\frac{n}{k})!)^{k}$. Therefore, the height of the decision tree must be $$ H \ge \log ((\frac{n}{k})!)^{k} = k \log (\frac{n}{k})! = \Omega(k \frac{n}{k} \log \frac{n}{k}) = \Omega(n \log \frac{n}{k}),$$ which is not the desired result $\Omega(n \log k)$.

What is wrong with my argument? And how to establish the lower bound $\Omega(n \log k)$?

Answer 1

From the result of $k$-sorting an array you can tell which elements of the original array were the $n/k$ smallest, the $n/k$ largest, and which belong to each of the other $k-2$ blocks of $n/k$ elements in between. In particular, there are at least $\binom{n}{n/k,\ldots,n/k}$ different leaves, which works out to $\frac{n!}{(n/k)!^k} = \exp \Theta(n\log k)$. This gives you the correct lower bound.

What you calculated is the number of different ways to completely sorted a $k$-sorted permutation. Therefore your lower bound is for sorting a $k$-sorted permutation, and for this task your lower bound is tight: a $k$-sorted permutation can be sorted in $O(n\log (n/k))$.