Question

Construct a permutation of the ten distinct elements (i.e. the digits 0,1,2,3,4,5,6,7,8,9) that is as bad as possible for quicksort using median-of-three partitioning. Please write out what the permutation is and describe how you found what it is.

Answer 1

In case of quicksort using median-of-three partitioning, the median of first , last and middle index element is selected as pivot with intention to avoid the worst case time complexity of O(n²) happens in traditional quick-sort when the array is already sorted and pivot element is either the first index or the last index.

Consider the permutation 1,9,3,4,0,5,6,7,8,2. Here the first indexed element is 1, last indexed element is 2, middle indexed element( index 5) is 0. Hence the median of 0,1,2 will be 1 and it will partition the array as

0 and 9,3,4,5,6,7,8,2 so that one sub array is of size 1 and another in size 8 which is worst possible partitioning in quicksort using median-of-three partitioning. Note that because we are selecting pivot as median of three elements, hence there will be atleast one element less than pivot and one element greater than pivot and hence both left and right subarray will have at least 1 element in all cases.

Hence the permutation 1,9,3,4,0,5,6,7,8,2 is worst possible permutation.

Please comment for any clarification.