4. Suppose that you are given n elements to sort. The lis of elements consists of n/k sub- sequences of k elements each. The elements in a sub-sequence are smaller than the elements in the following sub-sequence (a) Show hat (n lg k) is a lower bound on the number of comparisons required to solve this problem (b) Give an algorithm to sort the entire list in O(n lg k) average case. Prove your bound