Quicksort running in O(n^2) time? [duplicate]

Question

Can anyone explain why the worst-case runtime for quicksort is O(n^2) and why this is rare?

Answer 1

If the pivot is chosen in the worst way every time, rather than partitioning into two lists of size n/2, it will partition into one of size 1 and one of size n-1. This leads to a recursion depth of n and an n^2 total time.

This is rare because the pivot is normally chosen randomly, so the chances of picking the worst pivot every time are small, and on average the pivot will tend to split the list roughly in half.

If the pivot were chosen non-randomly, such as taking the first element, then certain inputs (pre-sorted or reverse-sorted lists) can force n^2 performance.