1. Suppose you have an array of N elements containing only two distinct keys, true and false. Give anO(N) algorithm to rearrange the list so that all false elements precede the true elements. You may use only constant extra space.
2. Suppose you have an array of N elements, containing three distinct keys, true, false, and maybe. Give an O(N) algorithm to rearrange the list so that all false elements precede maybe elements, which in turn precede true elements. You may use only constant extra space.
3. a. Prove that any comparison-based algorithm to sort 4 elements requires 5 comparisons.
b. Give an algorithm to sort 4 elements in 5 comparisons.