In‑place Stable Partition — methods, minimal‑memory patterns, trade‑offs

A concise technical dossier: what "stable, in‑place partition" means for arrays, the distinct algorithmic patterns to achieve it, small worked traces, annotated pseudocode sketches, and a compact ledger to choose among approaches.

Array silhouette showing stable partition by rotations Eight cells split by predicate; arrows indicate two rotations that move a suffix of true elements left while preserving order a b T1 c T2 d T3 e stable order preserved rotate suffix left
Silhouette: two rotation primitives move true-marked elements (T1,T2,T3) left while preserving their internal order.

Core question — short answer

Which in‑place stable partition fits your constraints? Roughly: rotation‑based patterns give true in‑place behaviour with simple invariants but may cost more time; divide‑and‑conquer trades extra stack for fewer element moves; small buffered approaches reduce moves at the price of bookkeeping proportional to buffer size k.

Worked example A — rotation sequence (n = 8)

Array (left‑to‑right): [a, b, T1, c, T2, d, T3, e]. Predicate: items labelled T* are "true". Goal: move T* left preserving their order T1,T2,T3.

a
b
T1
c
T2
d
T3
e

Step 1: rotate the block [c, T2, d, T3] left so T2 and T3 come just after T1

a
b
T1
T2
T3
c
d
e

Now the true items are contiguous and in original order: T1,T2,T3.

Rotation‑based method (concept)

Treat rotation as a primitive that moves a contiguous suffix or middle block left or right while preserving the order of elements inside moved blocks. Simple stable partition scans and performs rotations to gather true elements; invariants track contiguous blocks of false/true. Memory class: O(1) auxiliary. 

/* non‑executable pseudocode sketch (illustrative)
for i from 0 to n-1:
  if predicate(a[i]) then
    rotate block that moves a[i] left past preceding falses
  maintain: order within true-blocks unchanged
Note: naive per-element rotation can cost O(n^2) moves overall.

Block‑rotate / cycle decomposition (concept)

Decompose array into blocks and perform block rotations using reversal or cyclic swapping. Cycle decomposition (GCD-style) can move elements with minimal extra space but requires careful index math. These techniques aim to reduce element copies compared with naive rotations but add implementation complexity and delicate invariants.

Divide‑and‑conquer (recursive) approach

Recursively stable‑partition halves, then rotate the boundary to join true elements. Correctness invariant: halves individually stable, rotation preserves order across the join. Memory class: O(log n) stack; time typically better than naive rotations for large n because partitioning limits redundant moves. Implementation difficulty: moderate; watch recursion depth and rotation primitives. 

/* sketch: recursive stable partition (non‑executable)
stable_partition(a[l..r]):
  if small: perform small‑scale stable partition directly
  m = (l + r) / 2
  stable_partition(a[l..m])
  stable_partition(a[m+1..r])
  rotate to bring true elements from right half before false elements of left half
Invariant: order of true items remains as in original array.

Buffer‑limited strategies (O(k) auxiliary)

Keep a small buffer of size k to accumulate true items or false items and flush them as blocks. For example, a 2‑slot buffer reduces per‑element shifts by batching moves. Trade‑off: extra bookkeeping to manage buffer fill/flush and to preserve stability across flushes. Memory class: O(k); time often improved in practice over per‑element rotations when k>1.

Mini worked trace (k=2): scan, store two trues in buffer, shift preceding falses once, write trues in original order — stability preserved by buffer ordering.

Comparative ledger — quick chooser

R1
Naive rotations
memory: O(1)
time: O(n^2) in worst case • simple
R2
Block rotate / cycle
memory: O(1)
time: O(n)–O(n log n) depending on implementation • complex index math
R3
Divide & conquer
memory: O(log n) stack
time: often faster than naive; moderate complexity
R4
k‑buffer batching
memory: O(k)
time: fewer moves for k>1 • bookkeeping overhead

Worked example B — why stability matters

Suppose items are (city, population) pairs; predicate selects cities starting with 'A'. A stable partition preserves secondary ordering (population tie‑break) among cities that start with 'A' without an extra sort pass.

Austin
Boston
Albany
Chicago

After stable partition: [Austin, Albany, Boston, Chicago] — Austin precedes Albany as in the input; unstable partition might reorder them.

Legend & concise chooser

rotation arc — block movement
large numerals — section markers
italic annotations — design notes

Rules of thumb: choose constant‑memory rotation if memory is critical and n is small; use divide‑and‑conquer when n is large and stack recursion is acceptable; pick k‑buffer when you can afford small extra memory and want fewer element moves.

Further topics to read next (concepts): stable sorting relations, rotation via reversal, cycle decomposition, and library interface design for safe in‑place APIs.