Quicksort using Dutch National Flag Algorithm

Implement Quicksort efficiently for inputs containing many repeated elements.


Quicksort exhibits poor performance for inputs that contain many repeated elements. The problem is clearly visible when all the input elements are equal. Then at each recursion, the left partition is empty (no input values are less than the pivot), and the right partition has only decreased by one element (the pivot is removed). Consequently, the algorithm takes quadratic time to sort an array of equal values.

To solve this problem an alternative linear-time partition routine can be used that separates the values into three groups:

  • values less than the pivot
  • values equal to the pivot and
  • values greater than the pivot.

The values equal to the pivot are already sorted, so only the less-than and greater-than partitions need to be recursively sorted. This linear-time partition routine is similar to three-way Partitioning for Dutch national flag problem.


Download   Run Code


1 2 2 2 5 6 6 6 6 8


Download   Run Code


[1, 2, 2, 2, 5, 6, 6, 6, 6, 8]

The best case for the algorithm now occurs when all elements are equal (or are chosen from a small set of k « n elements). In the case of all equal elements, the modified quicksort will perform at most two recursive calls on empty subarrays and thus finish in linear time.

References: https://en.wikipedia.org/wiki/Quicksort

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

There is similar interesting problem that can be solved using dutch national flag algorithm.


On line 47, why are you returning this: return new Pair(start-1, mid);