Problem 3. (25 points) Describe and analyze an algorithm that takes an unsorted array A of n integers (in an unbounded range) and an integer k, and divides A into k equal-sized groups, such that the integers in the first group are lower than the integers in the second group, and the integers in the second group are lower than the integers in the third group, and so on. For instance if A {4.12.3.8.7.9. 10. 20.5) and k-3, one possible solution would be Ai = {4.3.5), A2-18, 7,9), A3-{12.10, 20). Sorting A in 0(n log n)-time would solve the problem, but we want a faster solution. The running time of your solution should be bounded by O(nk). For simplicity, you can assume that is n a multiple of k, and that all the elements are distict. Note: k is an input to the algorithm, not a fixed constant