Algorithms and data structures · Introductory

Quicksort: partition balance changes performance

Trace partitioning around a pivot and distinguish expected performance from the quadratic worst case.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Partition around a chosen pivot
  2. Work through a small partition
  3. Compare balanced and extremely skewed splits
  4. Account for stability and call-stack space
  5. Ask Logeia about this articleCheck your understanding

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.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path