Partitioning. Design a linear-time algorithm to sort an array of Comparable objects that is known to have at most two distinct values. Hint: Maintain two pointers, one starting at the left end and...

Partitioning. Design a linear-time algorithm to sort an array of Comparable objects that is known to have at most two distinct values. Hint: Maintain two pointers, one starting at the left end and moving right, and the other starting at the right end and moving left. Maintain the invariant that all elements to the left of the left pointer are equal to the smaller of the two values and all elements to the right of the right pointer are equal to the larger of the two values.