Supply an array containing integers 1 through 12 such that a quicksort algorithm using median of three will recurse to 6 levels, counting the top level as 0; showing that even with median of three, quicksort has worst case performance of O(n^2).

The pivot is then moved to the end and the partition is performed, then after the partition, the pivot moves to its rightful place.

Median of three: on the range [p, r], choosing as the split value the median of vals[p], vals[r], and vals[(p+r)/2].