Consider a comparison-based sorting algorithm for sorting an input sequence of n numbers (x1, x2, . . . , xn). Suppose that the sorting algorithm has the following additional information about the sequence to be sorted. The input sequence is a concatenation of n/k subsequences, each of which contains k elements. The sorting algorithm somehow knows that all the elements in each subsequence occur before all the elements in any later subsequence. Consequently, after each subsequence is sorted, the concatenation of all the sorted subsequences produces a sorted sequence. Using a decision tree argument, show that the lower bound on the number of comparisons needed to sort this sequence is (n log k).

That's all the info I have