A set S of numbers is partially sorted into k groups S1..Sk if every element of S is in exactly one subgroup, and every element of Si is less than or equal to every element in Si 1. Devise an efficient algorithm for partially sorting S into k groups, and analyze its running time. This problem can be solved in O(nlogk) time. For convenience, you may assume k is a power of 2.