The quicksort partition technique that you have learnt in class has a major problem. I'll illustrate the problem; you will have to fix it. Suppose, you can find the median of the array in O(n) time. You use the median as pivot to partition the array. Ideally, this will split the array into two roughly equal halves and ultimately result in an O(n log n) time quick-sort algorithm.

Recall the way the partition algorithm has been designed { all numbers less than equal to the median will be on the left half. So, if you have too many occurrences of the median, then you no longer get the half split, leading ultimately to an O(n2) time algorithm. For example, say the array is [1; 30; 5; 5; 3; 5; 5; 5]; then the median is 5. The split you get is [1; 5; 5; 5; 3; 5] and [30]; clearly, this is not a half split (in fact, nowhere near).

Fix the partition algorithm so that you achieve an O(n log n) time quick-sort algorithm when the median is provided at each recursion level; WRITE pseudo-code. Do not write a different partition algorithm; you have to modify the technique discussed in class.