Type PARTITION (Lomuto, CLRS 1-indexed)

Answer

PARTITION(A, p, r) x = A[r] i = p - 1 for j = p to r - 1 if A[j] <= x i = i + 1 exchange A[i] with A[j] exchange A[i+1] with A[r] return i + 1

i marks the boundary of the ≤x region; j scans the unknown region. On A[j] ≤ x grow the low side; the final swap drops the pivot between the two sides and returns its index.