Suppose that you are given a sequence of \(n\) elements to sort. The input sequence consists of \(n/k\) subsequences, each containing \(k\) elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length \(n\) is to sort the \(k\) elements in each of the \(n/k\) subsequences. Show an \(\Omega(n \lg k)\) lower bound on the number of comparisons needed to solve this variant of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)
Think of this problem as sorting \(n/k\) independent groups, where each group has \(k\) elements. While it’s tempting to say “each group needs \(\Omega(k \lg k)\) comparisons, so total is \(\Omega((n/k) \cdot k \lg k) = \Omega(n \lg k)\),” this reasoning is flawed because it doesn’t account for how information might transfer between groups.
Instead, we use the decision tree model properly.
A correct sorting algorithm must distinguish between all possible ways the elements within each subsequence can be arranged. For each of the \(n/k\) subsequences, there are \(k!\) possible internal orderings. Since the subsequences are independent, the total number of distinguishable input configurations is:
\[(k!)^{n/k}\]
Any comparison-based algorithm must have a decision tree with at least \((k!)^{n/k}\) leaves. If \(h\) is the height of this decision tree, then:
\[2^h \geq (k!)^{n/k}\]Taking logarithms:
\[\begin{align*} h &\geq \lg((k!)^{n/k}) \\ &= \frac{n}{k} \lg(k!) \\ &= \frac{n}{k} \cdot \Theta(k \lg k) \\ &= \Theta(n \lg k) \end{align*}\]Therefore, any comparison sort for this problem requires \(\Omega(n \lg k)\) comparisons in the worst case.