In Lomuto partitioning with the pivot at the high end, why must the final swap use i+1?
answer
- Write down what the scan guarantees at each moment
- Two regions: not greater, and greater
- What does i point at when the loop ends?
- That slot is already occupied by a small value
- The pivot belongs in the first large slot
basics
~20 sIn Lomuto partitioning, i is the last index of the region of values not greater than the pivot, so that slot is taken. The pivot belongs at i+1, the first larger slot; swapping into i strands a small value rightward.
solid answer
~40 sLomuto's scan maintains the invariant that `a[lo..i]` holds values `<= pivot` and `a[i+1..j-1]` holds values `> pivot`, with `a[hi]` parked as the pivot. So `i` is the **last** small slot, already full, and `i+1` is the **first** large slot — where the pivot belongs once the scan ends. Swapping `a[i+1]` with `a[hi]` evicts a large element to the far end, where it is correctly greater than the pivot, and lands the pivot at its final sorted index. Using `i` instead sends a value `<= pivot` out to `a[hi]`, right of strictly larger elements, and the recursive calls never move it back — the output is unsorted. The other half of the contract is the return value: it must be the pivot's index, and both sides must exclude it, or the recursion never terminates.
code
pseudocode · 10 linespartition(a, lo, hi):
pivot = a[hi]
i = lo - 1 // <= region is empty so far
for j in lo..hi-1:
// invariant: a[lo..i] <= pivot, a[i+1..j-1] > pivot
if a[j] <= pivot:
i = i + 1
swap(a[i], a[j])
swap(a[i + 1], a[hi]) // first large slot <-> pivot
return i + 1go deeper
Know that partitioning rearranges a range around a chosen pivot and hands back the index where that pivot ends up. Be able to point at the boundary index and say which side of it holds the smaller values.
State the loop invariant out loud — everything up to the boundary is not greater than the pivot, everything after it up to the scan position is greater — and derive the final swap position from it rather than reciting the line.
Show how you catch this in review: name the symptom it produces, say why short manual traces miss it, and point at the property a test should assert instead of eyeballing the output.
Own the decision of whether hand-written partition code belongs in your codebase at all, given that its failure mode is silent near-correctness, and set the standard for what a sorting primitive must be tested against before it ships.
## The scheme in one paragraph Lomuto partitioning parks the pivot at the high end of the range and sweeps a single scan index `j` from `lo` to `hi-1`. A second index `i` marks the boundary of the region already known to hold values `<= pivot`. Whenever `a[j] <= pivot`, the boundary advances (`i = i + 1`) and `a[i]` is swapped with `a[j]`, moving the small value into the small region and the large value it displaced out to where the scan has already passed. One pass, one extra index, easy to write from memory — which is why it is the version most people learn, and why its one boundary detail is a standard review question. ## The invariant At the top of every iteration, with the scan about to look at `a[j]`: - `a[lo .. i]` — all values `<= pivot` - `a[i+1 .. j-1]` — all values `> pivot` - `a[j .. hi-1]` — not yet examined - `a[hi]` — the pivot itself, untouched `i` starts at `lo - 1`, which correctly describes an **empty** small region. Both branches preserve the invariant. If `a[j] > pivot`, nothing moves and the large region simply grows by one slot. If `a[j] <= pivot`, then `i` advances into the first large slot, the swap puts the small value there and sends the large value that lived there out to index `j`, which is exactly where the large region now ends. ## Why the pivot goes to i+1 Read the invariant at the moment the loop exits, when `j == hi`: - `a[lo .. i]` are all `<= pivot` - `a[i+1 .. hi-1]` are all `> pivot` - `a[hi]` is the pivot Index `i` is the **last occupied slot of the small region** — it holds a real value that must stay left of the pivot. Index `i+1` is the **first slot of the large region**, and everything from there to `hi-1` is greater than the pivot. So the pivot's sorted position is `i+1`: every element to its left is `<= pivot`, every element to its right is `> pivot`. `swap(a[i+1], a[hi])` puts it there and, in the same move, sends the large element that occupied `i+1` to `hi`, where it is still correctly to the right of the pivot. Return `i+1`. What does the off-by-one do? `swap(a[i], a[hi])` writes the pivot over a slot whose value was `<= pivot` and throws that small value all the way out to `hi` — past the entire `> pivot` region. Now the split is a lie: the caller is told everything right of the returned index exceeds the pivot, but the last slot holds a value below it. The recursive calls sort `lo..i-1` and `i+1..hi` independently and never compare that stranded element against anything on the left again, so it stays on the wrong side. The result is a nearly-sorted output with a small number of misplaced values — the nastiest kind of bug, because it passes eyeball checks on short inputs and only shows up when a test asserts full order or a downstream binary search misses. ## The other boundary that reviewers check The return value and the recursive calls form one contract: ``` quicksort(a, lo, hi): if lo < hi: p = partition(a, lo, hi) quicksort(a, lo, p - 1) quicksort(a, p + 1, hi) ``` The pivot at `p` is **final** — it is in its sorted position and must be excluded from both sides. Including it (`quicksort(a, lo, p)`) leaves a subrange the same size as its parent whenever the pivot lands at the top, and the recursion never terminates. A partition that returns an index which is *not* the pivot's resting place breaks this same contract in a subtler way. ## Why the comparison must be `<=` and not `<` With `<`, an element equal to the pivot is treated as large. That is still correct — the pivot's final position is well defined either way — but it is a load-bearing detail on duplicate-heavy input, and flipping it is a second classic diff-review catch. ## Contrast with the two-index scheme Hoare's original partition walks two indices inward from both ends, swapping an out-of-place pair on each meeting, and returns a **split point**, not a pivot position — the pivot is not necessarily at the returned index and is not guaranteed final. The recursive calls therefore look different: the boundary index must be *included* in one side (`lo..p` and `p+1..hi`), and copying Lomuto's `p-1` / `p+1` calls onto a two-index partition is the exact mistake that produces either an unsorted result or unbounded recursion. Also note the two schemes are not interchangeable in behaviour: on ranges full of equal keys, the one-sided `<=` scan sends everything to one side, while a two-index scan that stops on equal keys splits near the middle. Knowing which contract a partition function is offering — pivot index or split point — is the whole skill this question tests.
- What symptom would you actually see if the final swap used i instead of i+1?Almost-sorted output with a few values stranded to the right of larger ones, one per bad partition call. Short hand-checked inputs often look fine, so it slips review; it surfaces when a test asserts full order across a long input, or when a downstream lookup that assumes sorted order silently misses. It is a correctness bug, not a performance bug.
- Why must both recursive calls exclude the returned pivot index?Because the pivot at that index is already in its final sorted position, and because excluding it is what guarantees progress. If a recursive call includes it, a partition whose pivot lands at the top of the range produces a subrange the same size as its parent, and the recursion never terminates. Excluding it means the two sides together hold n-1 elements, so every level strictly shrinks.
- A two-index partition returns a boundary rather than a pivot index — what changes in the caller?The boundary is a split point, not a final position: the pivot may sit on either side and is not guaranteed placed. The recursive calls must cover the boundary element, sorting lo..p and p+1..hi rather than skipping an index. Reusing the one-sided partition's p-1/p+1 calls against it drops or double-counts an element, giving wrong output or non-terminating recursion.
saying these in an interview costs you the question
- Says i marks the pivot's final position during the scan
- Cannot state the invariant the two regions satisfy
- Calls the off-by-one a performance issue rather than wrong output
- Includes the returned pivot index in a recursive call
- Assumes any partition function returns a placed pivot index
- Thinks swapping with the last index is always safe because the pivot lives there