Implement the following modification of the quick sort algorithm, due to Bentley and McIlroy. Instead of using the first element as the pivot, use an approximation of the median. (Partitioning at the actual median would yield an O(n log(n)) algorithm, but we don't know how to compute it quickly enough.)

If n < or = 7, use the middle element. If n < or = 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(v0, v1, v2), med(v3, v4, v5), med(v6, v7, v8)).

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?