The pivot is a third pointer
Updated
Besides L and R (or low and high), keep p as the pivot index. Lomuto: p = n-1, j scans, i writes values < a[p], then swap a[i] with a[p]. p does not hunt. It holds the pivot slot.
What to focus on
After the pass, a[p] sits at its final split. Left of p is < pivot. Right of p is ≥ pivot. Do not let L/R overwrite p until the closing swap.
Worked examples
pivot at end
a = [1, 9, 1, 4], p=3 pivot 4, i=0- j=0: 1<4 swap i=0, i=1
- j=1: 9≥4 skip
- j=2: 1<4 swap i=1 → [1, 1, 9, 4], i=2
Result: swap i with p → [1, 1, 4, 9], p=2
already home
a = [1, 4, 9], p=1 pivot 4- left of p is 1<4
- right is 9>4
- no swap needed if you already split
Result: p stays 1
single
a = [7], p=0- j never runs
- swap i=0 with p=0
Result: p=0, a = [7]
Try it
Write lomuto(a). a is an array of integers. p = n-1 holds the pivot value. i is the write index. j is the scan index. The last swap puts the pivot at p. Return p. On [1, 9, 1, 4] the last swap puts 4 at p. Repeat on [1, 2, 3, 9].
a is nonempty, length ≥ 2. p = n-1 holds the pivot value.