Partition-Style Pointers

## What a partition pass actually does Partitioning takes a collection and a test — either "compare against this pivot value" or a plain yes/no predicate — and rearranges the elements in place so that all the elements failing the test come before all the elements passing it. It returns (or leaves behind) a **boundary index**: the position where one region ends and the other begins. A useful running example: an incident queue where each record carries a numeric priority, and you want every record above a paging threshold moved to the front so the on-call tooling can walk a contiguous block. One linear sweep with exchanges does it, without allocating a second queue. ## The invariant, stated precisely Write the collection as `a[0..n-1]` and let `b` be the boundary the pass returns. When the pass finishes: - every element in `a[0..b-1]` compares at most equal to the pivot; - every element in `a[b..n-1]` compares at least equal to the pivot. That is the entire post-condition. Everything a beginner tends to *also* believe is absent from it. ## What is guaranteed versus what is not | Claim | True after one pass? | |---|---| | Two regions, separated by a known boundary | Yes | | Each region is internally sorted | No | | The two regions have equal size | No | | The boundary sits near the middle | No | | Relative order of equal elements is kept | No | | The pivot element itself sits at its final sorted index | Only in some schemes | The last row is worth dwelling on. In the common left-to-right scheme the pivot is swapped into the boundary slot at the very end, so it genuinely is in the position it would occupy in the fully sorted collection — one element is permanently placed by one linear pass. In the two-ended scheme the pass returns a split point and never fixes the pivot anywhere in particular; a caller that assumes otherwise and excludes the returned index from further work will silently drop an element. So "partition places the pivot" is a property of a *specific* scheme, not of partitioning. ## Why the split can be maximally uneven If the pivot happens to be the largest value present, every other element compares at most equal to it and the boundary lands at the last index, leaving the other region empty. Nothing is broken — the invariant still holds, the pass still cost `O(n)` — but a caller that assumed "about half" has assumed something the pass never promised. Balance is a property of *which pivot you picked*, not of the partitioning machinery. ## Cost One pass examines each element once, so the time is linear in the number of elements, `O(n)`, with `n - 1` or `n` comparisons depending on how the pivot is excluded. Three-way variants may compare an element twice, which is still `O(n)`. Extra space is `O(1)` because the algorithm only ever swaps elements already present — no second collection, no copy. That is exactly why the technique earns its place: it is the cheapest possible way to convert "which group does this belong to?" into "which side of index `b` does it sit on?". ## Pivot versus predicate The pivot framing ("at most this value" / "at least this value") is the one that shows up inside sorting, but the same two-pointer machinery works for any predicate: contractor versus employee, expired versus live, above threshold versus below. With a predicate there is no pivot element to place, so only the boundary is meaningful. Recognising that the pivot is just a convenient way to *express* a predicate is what lets you reuse the pattern outside sorting. ## The interview failure mode Asked "what does partition give you?", weak candidates answer "it sorts the halves" or "it puts the pivot in the middle". Both overclaim. The correct answer is deliberately modest — one boundary, two unordered regions, linear time, constant extra space — and the modesty is the point: a guarantee that weak is cheap enough to run inside a loop, and it is still strong enough that a caller who only needs to know *which side* an element is on never has to look further.