Bentley and McIlroy suggest the following modification to the quicksort algorithm when dealing with data sets that contain many repeated elements. Instead of partitioning as

(where ≤ denotes the elements that are ≤ the pivot), it is better to partition as

However, that is tedious to achieve directly. They recommend to partition as

and then swap the two = regions into the middle. Implement this modification and check whether it improves performance on data sets with many repeated elements.

Al VI