Quick sort is to partition the array around one element and then sort each part recursively. We pick up one element as the pivot and then move all elements less than the pivot to the left, and all elements greater than the pivot to the right.
We then recurse on the left and right parts. In a case of an array that contains many duplicates, quicksort will recurse on all duplicates of the pivot element.
You are to develop a new partitioning function that works better on arrays with duplicates. The idea is to partition the array into elements less than the pivot, equal to the pivot and greater than the pivot. 2
(a) Write a pseudocode for your suggested partitioning algorithm. Make sure your algorithm is in-place (i.e., do not use more than a constant amount of extra space).
(b) Using your suggested partitioning algorithm in part (a), come up with a sorting algorithm. Analyze the worst-case running time of your algorithm.
(c) Find an array on which the original quicksort runs in time ?(n 2 ) but your algorithm from (b) runs in ?(n).