Implement the following modification of the quicksort algorithm, due to Bentley and McIlroy. Instead of using the first element as the pivot, use an approximation of the median.

If n ≤ 7, use the middle element. If n ≤ 40, use the median of the first, middle, and last element. Otherwise compute the “pseudomedian” of the nine elements a[i * (n - 1) / 8], where i ranges from 0 to 8. The pseudomedian of nine values is med(med(v₀, v₁, v₂), med(v₃, v₄, v₅), med(v₆, v₇, v₈)). Compare the running time of this modification with that of the original algorithm on sequences that are nearly sorted or reverse sorted, and on sequences with many identical elements. What do you observe?