Can anyone give an example for worst case of quick sort if we employ median of three pivot selection?

Question

If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also can anyone give an example including integers?

Thanks.

Note: I have searched online for quicksort's worst case, but all of them are referring to quicksort wherein the pivot is either the first element or the last element, but what I want is completely different.

Answer 1

If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also can anyone give an example including integers?

The worst case is when the selected pivot reduces the problem size by the smallest possible amount, i.e. provides as lopsided a partition as is possible. For the median of three elements, that cannot be either the largest or smallest valued element (assuming distinct values), as the definition of median ensures that in median of 3, there is one larger and one smaller element than the median.

For the rather poor but all too common case of using the median of the first, middle, and last elements (with distinct valued input), that worst case occurs when the median of the three is the second-smallest or second-largest valued element (because the largest or smallest is one of the other two of those three). That can occur when an in-order sequence of elements is rotated by just one position. Here are two examples:

1 2 3 4 5 6 7 8 0 (median of 1,5,0 is 1)

8 0 1 2 3 4 5 6 7 (median of 8,3,7 is 7)

When median of first, middle, last pivot selection is combined with most commonly used partitioning methods, the result is disastrous; each partition peels off two elements (the pivot and one extreme value) and leaves another rotated sequence remaining. The combination of first, middle, last pivot selection and a partitioning method which swaps the pivot to the first (or last) array position (rather common) is worse; it also generates rotated sequences when the input is reverse-sorted (e.g. 8 7 6 5 4 3 2 1 0).

See https://github.com/brucelilly/quickselect/blob/master/lib/libmedian/doc/pub/generic/paper.pdf and/or the video at https://www.youtube.com/watch?v=iWmAf4RMMiM for details and examples of some widely-used implementations that exhibit this behavior.

When input values are not distinct, another bad case for median of first, middle, and last elements is "organ-pipe" (bitonic) input, such as

0 1 2 3 4 3 2 1 0 (median of 0,4,0 is 0)

In the case of organ-pipe input, use of first, middle, and last elements is the worst possible choice of three elements for pivot selection!