Finding a lower bound for the amount of comparisons for sorting $k$ subarrays with $\frac n k$ elements

Question

Let the input be an array of $n$ elements, with $k$ sets $S_1,...,S_k$ such that each set has $\frac n k$ elements. The elements in each $S_i$ are larger than the elements in $S_{i-1}$.

1. Find an algorithm that sorts the input in $O(n\log (\frac n k ))$ runtime.

2. Find a lower bound for the minimal amount of comparisons in the worst case.

1. is pretty simple I think:

   for each S_i
      mergesort(S_i[n/k])
   

But with 2. I get results that can't be right: in the worst case there would have to be at least $(\frac n k )!$ comparisons for each $S_i$ because the algorithm will have to pass each combination at least once, also, this is the amount of leaves at the lowest level of the decision tree.

This gives: $T_{worst}(n) = \Omega (k(\frac n k )!)$ which is a lot larger than $O(n\log (\frac n k ))$. So what am I doing wrong here?

Answer 1

If a decision tree has at least $m$ leaves then its height is at least $\log_2 m$. It is the height that bounds the number of comparisons rather than the number of leaves. In your case there are $(n/k)!^k$ leaves, and so $\Omega(\log[(n/k)!^k]) = \Omega(n\log(n/k))$ comparisons.