1. Suppose we want to partition N items into G equal-sized groups of size N/G, such that the smallestN/G items are in group 1, the next smallest N/G items are in group 2, and so on. The groups themselves do not have to be sorted. For simplicity, you may assume that N and G are powers of two.

a. Give an O(N log G) algorithm to solve this problem.

b. Prove an 0.(N log G) lower bound to solve this problem using comparison-based algorithms.

2. Give a linear-time algorithm to sort N fractions, each of whose numerators and denominators are integers between 1 and N.

3. Suppose arrays A and B are both sorted and both contain N elements. Give an O(log N) algorithm to ?nd the median of A ∪ B.