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?