A strong answer
Quick sort partitions the array around a pivot, putting smaller elements before it and larger after, so the pivot lands in its final position, then recurses on the two sides. Partitioning is a single linear scan with occasional swaps.
The running time depends on how balanced the splits are. Perfect splits give log₂ n levels of O(n) work, so O(n log n). Splits don't need to be perfect: even if every split were 90/10, the depth would be about 6.6 log₂ n, still O(n log n). With a random pivot, the expected comparisons are about 1.39 n log₂ n on every input, because the randomness is in the algorithm, not the data.
The worst case comes from consistently extreme pivots, for example always choosing the first or last element on sorted input: each partition peels off one element, giving n levels and about n²/2 comparisons, plus O(n) stack depth.
In practice it is fast because the inner loop is a compare and an occasional swap, both scans are sequential and cache-friendly, it sorts in place with no buffer to copy into, and subarrays quickly fit in cache. Real implementations remove the worst case: median-of-three or random pivots, recursing into the smaller side to bound the stack at O(log n), three-way partitioning for duplicates, insertion sort for small pieces, and introsort's fallback to heap sort when recursion exceeds about 2 log₂ n, which makes the worst case O(n log n).
What the interviewer is listening for
- The partition step and the pivot's final position.
- Why imperfect splits still give O(n log n), and what makes the worst case.
- Concrete reasons for its practical speed.
- The defenses used by C++, Java, Go or Rust.
Common mistakes
- Saying the average case assumes random input, when a random pivot makes it hold for every input.
- Forgetting stack depth in the worst case.
- Claiming it is always faster than merge sort; it isn't stable and isn't suited to linked lists or external data.