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


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.
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]
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?
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.