Give an algorithm in 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