With random pivot selection, quicksort is expected O(n log n) time for all inputs. (The expectation is over the set of random numbers used to pick the random pivots, and doesn't involve the input at all). Algorithms like this are called "las-vegas".
Yes. And if your adversarial algorithm is good enough, it should work even in that case. (Of course any input is the worst case if all inputs have the same expected time.)
