Analysing worst-case time complexity of quick-sort in different cases

Question

I am trying to understand worst case time complexity of quick-sort for various pivots. Here is what I came across:

1. When array is already sorted in either ascending order or descending order and we select either leftmost or rightmost element as pivot, then it results in worst case $O(n^2)$ time complexity.

2. When array is not already sorted and we select random element as pivot, then it gives worst case "expected" time complexity as $O(n \log n)$. But worst case time complexity is still $O(n^2)$. ^[1]

3. When we select median of ^[2] first, last and middle element as pivot, then it results in worst case time complexity of $O(n \log n)$ ^[1]

I have following doubts

D1. Link [2] says, if all elements in array are same then both random pivot and median pivot will lead to $O(n^2)$ time complexity. However link [1] says median pivot yields $O(n \log n)$ worst case time complexity. What is correct?

D2. How median of first, last and middle element can be median of all elements?

D3. What we do when random pivot is $i$th element? Do we always have to swap it with either leftmost or rightmost element before partitioning? Or is there any algorithm which does not require such swap?

Answer 1

There is no one QuickSort. There is one original, which we only care about for historical reasons, and many variations, all different.

In the case of n identical items, different implementations will run in O(n log n) or O (n^2). Since this is a practical case, the latter kind of algorithm should be avoided.

Your point (3) is wrong. Worst case for n different items is always O(n^2). In case (2) it doesn’t matter if the array is already sorted.

Taking a random element as the median makes sure that an opponent cannot create an array that takes n^2 steps to sort. Median of three random elements will usually partition the array better and therefore will be faster.

But apart from the case of taking the first or last element with a sorted array, and problems with all or many identical items, bad behaviour won’t happen unless you have an attacker that can create the data to be sorted, or with extraordinarily bad luck.

Answer 2

The usual rule here is only one question per post.

Link [2] doesn't say that random pivot and median pivot lead to $O(n^2)$ time complexity.

The median of first, middle, and last element is not the median of the whole array. Writing "median pivot" is probably a bad idea, unless you have carefully specified what that's a median of.

Link [1] says that taking the median of all elements leads to $O(n \log n)$ time complexity. That's different than taking the median of first, middle, and last. Also, it's rare for practical implementations to take the median of all elements, as that link already states.