When implementing quicksort, if the array contains lots of duplicates, it may be better to perform a three-way partition (into elements less than, equal to, and greater than the pivot), to make smaller recursive calls. Assume three-way comparisons, as provided by the compareTo method.

Give an algorithm (pseudocode/Java) that performs a three-way in-place partition of an N -element subarray using only N ? 1 three-way comparisons. If there are d items equal to the pivot, you may use d additional Comparable swaps, above and beyond the two-way partitioning algorithm. (Hint: As i and j move toward each other,

maintain five groups of elements as shown below):

EQUAL SMALL UNKNOWN LARGE EQUAL

i j