Sedgewick introduced a version of Quicksort that partition's its elements into 3 sections rather than 2, following an idea suggested by E. Dijkstra. What is the main reason to use the 3-way Quicksort

3-way quicksorth is used

If the array includes many duplicates

Explanation:

In simple QuickSort algorithm, we select an element as pivot, partition the array around pivot and recur for subarrays on left and right of pivot.

Consider an array which has many redundant elements. For example, {1, 4, 2, 4, 2, 4, 1, 2, 4, 1, 2, 2, 2, 2, 4, 1, 4, 4, 4}. If 4 is picked as pivot in Simple QuickSort, we fix only one 4 and recursively process remaining occurrences.