Partition around a chosen pivot
Quicksort chooses a pivot, partitions elements according to their relation to it, and recursively sorts the remaining ranges. After partitioning, the elements inside the smaller and larger ranges are not necessarily sorted yet. The method has many variants: pivot selection, in-place versus separate storage, and the treatment of equal keys all matter. A two-way partition and a three-way partition that isolates equal keys can behave quite differently on duplicate-heavy input. Describe the actual partition contract before reasoning about the recursive calls.
Work through a small partition
For [4, 1, 3, 2], take three as the pivot. Conceptually group [1, 2] below it, [3] equal to it, and [4] above it. The remaining subproblems are now small. This illustration describes the grouping, not the exact intermediate order produced by every in-place partition implementation. An implementation can maintain boundaries between regions already known to satisfy a condition and a region still being examined. Swaps and boundary updates must preserve those claims, particularly when the scan encounters a value equal to the pivot.
Compare balanced and extremely skewed splits
Reasonably balanced partitions yield logarithmically many recursion levels with linear total partition work per level. With a suitable randomized pivot strategy, standard quicksort has expected O(n log n) time. That is not an unconditional worst-case bound. A naïve strategy that always chooses the first value can repeatedly split ascending input into an empty range and a range of size n − 1. The total work then follows n + (n − 1) + … and becomes quadratic. State whether a performance claim is expected, average under an input model, or worst-case.
Account for stability and call-stack space
Typical in-place quicksort does not preserve the input order of equal-key items, so it is not a stable sort. If that order matters, choose a suitable variant or another algorithm. Avoiding a large merge buffer also does not remove recursion-stack costs. An unbalanced recursion can consume substantial stack space. Recursing only on the smaller partition and iterating on the larger one is one technique for controlling that space. In practical selection, consider equal-key frequency, pivot selection, comparison cost, stability requirements, and the implementation’s fallback strategy, rather than treating all quicksort variants as interchangeable.