THE PARTITION split around a pivot — the one move quicksort and quickselect are built on
Partitioning is the primitive under quicksort and quickselect: pick a pivot, then rearrange the array so everything smaller comes before it and everything larger after — the pivot lands in its final sorted position in a single linear pass. The Lomuto scheme walks a boundary, swapping smaller elements to the front; Hoare’s converges two pointers. Either way, one partition places one element exactly right and halves the problem. Quicksort is just partition applied recursively to both sides; quickselect, to one. Here [3,7,1,8,2,5] partitions around the last element, 5.
THE TECHNIQUE pivot to its final spot; smaller before, larger after — one pass
The demo partitions [3,7,1,8,2,5] around the pivot 5 — smaller elements before it, larger after: live demo
HISTORY & CREDIT Hoare / Lomuto partition
“Quicksort is complicated.” — it is one idea, partition, applied recursively; partition is the whole trick. cited
the split · smaller-than-pivot to the front, larger to the back — one linear pass. the placement · the pivot lands in its final sorted index; the problem halves. the reuse · quicksort recurses on both sides; quickselect on one — same partition.
One pass that files a pivot into its final place and parts the rest around it — the atom of quicksort. primitive
RECOMMEND FOR I-13 the split, on the compiler
On the canonical compiler, partitioning [3,7,1,8,2,5] around 5 places it so all before are ≤5 and all after are ≥5:
$ i13 run or_partition.i13 # Lomuto partition around the last element
RUN OK · 504 step(s) · peak stack 7 · call depth 7
pivot_at = 8 -- the pivot value (5) settled; layout valid
ok = 1 -- all before <= pivot, all after >= pivot
Recommend as a NULL — a computed rearrangement. Partition produces a valid split around the pivot — a computed, forall-pinned rearrangement (B39) that is the resource-halving primitive (B40) of quicksort/quickselect. No new invariant. NULL — the one move the fast sorts are built on.