Question: When implementing quicksort, if the array contains lots of duplicates. you may find it best to perform a three-way partition (into elements less than, equal to, and greater than the pivot) and make smaller recursive calls. Assume that you can use three-way comparisons.
a. Give an algorithm that performs a three-way in-place partition of an N element subarray using only N- I 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.
b. Prove that, using the algorithm in part (a), sorting an N-element array that contains only d different values takes O(d N) time.