Challenge: Improving Quicksort

The $QuickSort$ algorithm becomes slow when the input array contains many repeated elements. For example, when all elements in the input array are the same, the partition procedure splits the array into two parts, one empty part and the other part with $n − 1$ elements. Since $QuickSort$ spends $a \cdot n$ time to perform this partition, its overall running time is:

$$a \cdot n + a \cdot (n − 1) + a \cdot (n − 2) + \ldots = a \cdot \frac{n \cdot (n + 1)}{2}$$