Quicksort Idea

Quicksort chooses a pivot, partitions into smaller/larger, and recursively sorts the sides. Expected time $O(n \log n)$, Worst Case $O(n^{2})$ with poor pivots.

Randomized pivot or median-of-three reduce the worst case.

Partition without a full sort: Kth Largest Element in an Array [1].

Where used

In-place average $O(n \log n)$, dual-pivot in the JDK for primitive arrays. Pivot strategy determines worst cases and robustness against adversarial input.

Depth

Quicksort selects a pivot element and organizes the remaining values into regions relative to the pivot. Then, the regions are sorted recursively. Unlike Merge Sort, it invests linear work before the recursive calls in a partitioning.

Balanced subregions result in low recursion depth and very good average runtime. Repeatedly extremely unbalanced partitions create nearly linear depth and quadratically increasing total work. Randomly or robustly chosen pivots mitigate this risk.

Difficulty levels

1. Distinguish between pivot selection, partition, and recursion as phases.
2. Compare recursion trees for balanced and skewed partitions.
3. Assess pivot strategies for pre-sorted and duplicate-rich data.

Pitfalls

The pivot is a value concept, and its position can change during partitioning. Recursive bounds must exclude already completed regions; otherwise, infinite loops may occur.