15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Lomuto partition takes the last element as the pivot and scans left to right with a boundary index. Each value smaller than the pivot swaps into the boundary slot, and the boundary moves up. A final swap puts the pivot at the boundary: smaller values sit left of it, the rest right. It costs O(n) time and O(1) space.
| Pivot | Last element A[hi], stored before the scan |
|---|---|
| Result | Values < pivot on the left, values >= pivot on the right |
| Time | O(m) for a range of length m, m - 1 comparisons |
| Extra space | O(1): pivot, i and j |
| Returns | The pivot's final index; neither side is sorted |
Assume you can read a sorting contract: a sorting procedure must preserve the input values while arranging them according to an order. It also assumes you have seen in-place array updates, such as swaps.
Partitioning does not complete sorting.
Choose one value as the pivot. Rearrange an active array range so that:
The values within either side do not have to be sorted.
The procedure uses a last-element pivot and a strict comparison:
< pivot go left,>= pivot go right.Equal values therefore go to the right side of the placed pivot.
Use this array.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Value | 3 | 1 | 4 | 2 |
The pivot is the last value, 2, at index 3.
Scan the nonpivot values from left to right. A boundary index named i marks where the next value less than 2 belongs.
At the start:
i = 002 is stored before scanning1[3, 1, 4, 2]
2 i
3 j pivotThe region before i is the less-than-pivot region. It is empty initially.
Start with the pivot value stored as 2 and the boundary at i = 0.
The scan value is 3.
3 < 2 is false, so do not swap. This value belongs in the greater-than-or-equal region.
Partition [3, 1, 4, 2] around the last value 2: scan j left to right; a value < 2 swaps into position i and i advances. A final swap puts the pivot at index 1: [1, 2, 4, 3].
The array remains:
1[3, 1, 4, 2]The scan value is 1.
1 < 2 is true. It belongs in the less-than region, at the boundary index i = 0.
Swap the values at indices 1 and 0.
1Before swap: [3, 1, 4, 2]
2Swap indices 1 and 0
3After swap: [1, 3, 4, 2]Now advance the boundary.
1i = 1The state is now:
1Indices: 0 1 2 3
2Values: [1, 3, 4, 2]
3 i j pivotIndex 0 contains 1, which is less than 2.
The scan value is 4.
4 < 2 is false, so do not swap.
1[1, 3, 4, 2]
2 i j pivotThe scan is now finished. The boundary is still i = 1.
Everything before index 1 is less than 2. The values from index 1 through index 2 are greater than or equal to 2.
Swap the pivot at index 3 with the boundary value at index 1.
1Before swap: [1, 3, 4, 2]
2Swap indices 3 and 1
3After swap: [1, 2, 4, 3]The pivot is now at index 1.
The partition result is:
1[1, 2, 4, 3]1 is less than 2. Both 4 and 3 are greater than or equal to 2.
The array is not globally sorted because the right side is [4, 3].
Before every scan position j:
i are less than the pivot.i through j - 1 are greater than or equal to the pivot.j onward have not been classified yet, except for the stored pivot at the final active position.These conditions form the loop invariant.
Just before scanning 4 at index 2:
1[1, 3, 4, 2]
2 <2 >=2 ? pivot[1] is the less-than region.[3] is the greater-than-or-equal region.[4] has not yet been classified.[2] is reserved as the pivot.The boundary i always points to the first open position in the less-than region.
Use an inclusive active range from lo through hi.
A[hi] as the pivot value.i to lo. The less-than region starts empty.j from lo through hi - 1. Do not scan the pivot cell.A[j] < pivot, swap A[i] and A[j], then increment i.
A[j] in place.
A[i] and A[hi].
i, the pivot’s final index.Store the pivot value before scanning. Reserve the final pivot cell until the final swap.
Procedure contract
partitionLastPivot(A, lo, hi)
A; inclusive active range [lo, hi].0 <= lo <= length(A) and lo - 1 <= hi < length(A). An empty range has hi < lo.p for a nonempty range. For an empty range, returns lo without changing the array.p is returned, then:
A[k] for lo <= k < p is < A[p],A[k] for p < k <= hi is >= A[p],Helper contract
swap(A, x, y) exchanges the values at valid array indices x and y. It mutates A and returns no value.
11 procedure partitionLastPivot(A, lo, hi) -> integer
22 if hi <= lo
33 return lo
44
55 pivot <- A[hi]
66 i <- lo
77
88 for j <- lo to hi - 1
99 if A[j] < pivot
1010 swap(A, i, j)
1111 i <- i + 1
1212
1313 swap(A, i, hi)
1414 return iRun partitionLastPivot(A, 0, 3) on:
1A = [3, 1, 4, 2]| Line | Action | A | i | j |
|---|---|---|---|---|
| 2 | Is hi <= lo? Is 3 <= 0? No. | [3,1,4,2] | — | — |
| 5 | Store pivot <- A[3] | [3,1,4,2] | — | — |
| 6 | Set i <- 0 | [3,1,4,2] | 0 | — |
| 8 | Start loop with j = 0 | [3,1,4,2] | 0 | 0 |
| 9 | Is A[0] < pivot? Is 3 < 2? No. | [3,1,4,2] | 0 | 0 |
| 8 | Next loop position: j = 1 | [3,1,4,2] | 0 | 1 |
| 9 | Is A[1] < pivot? Is 1 < 2? Yes. | [3,1,4,2] | 0 | 1 |
| 10 | swap(A, 0, 1) | [1,3,4,2] | 0 | 1 |
| 11 | Increment i | [1,3,4,2] | 1 | 1 |
| 8 | Next loop position: j = 2 | [1,3,4,2] | 1 | 2 |
| 9 | Is A[2] < pivot? Is 4 < 2? No. | [1,3,4,2] | 1 | 2 |
| 8 | The loop ends because j has reached hi - 1. | [1,3,4,2] | 1 | — |
| 13 | swap(A, 1, 3) | [1,2,4,3] | 1 | — |
| 14 | Return i | [1,2,4,3] | returns 1 | — |
The returned pivot index is 1.
1[1, 2, 4, 3]
2 <2 pivot >=2For a nonempty active range, let pivot be the value stored from A[hi].
Before the loop:
i = lo,j = lo,i is empty,i through j - 1 is also empty.An empty less-than region contains only values less than the pivot. An empty greater-than-or-equal region also satisfies its requirement. The invariant holds before scanning starts.
Assume the invariant holds before scanning position j.
There are two cases.
Case 1: A[j] < pivot
The algorithm swaps A[j] with A[i].
i is less than the pivot.i < j, the old value at A[i] belonged to the greater-than-or-equal region. It moves to index j, where it remains in that region after i advances.i = j, the swap changes no positions, and the scanned value becomes part of the less-than region.i sets the boundary immediately after the enlarged less-than region.The invariant holds for the next scan position.
Case 2: A[j] >= pivot
The algorithm does not swap.
The scanned value stays at index j. It extends the greater-than-or-equal region by one position. The less-than region is unchanged. The invariant holds for the next scan position.
The loop scans every index from lo through hi - 1. When it ends:
i contains a value less than the pivot,i through hi - 1 contains a value greater than or equal to the pivot.The final swap places the pivot at index i.
i to index hi, if any, was greater than or equal to the pivot.After the swap, every value left of the returned index is less than the pivot, and every value right of it is greater than or equal to the pivot.
The procedure rearranges through swaps only, so it preserves the values in the active range.
It does not establish any order within either side. In [1,2,4,3], the right side [4,3] still needs sorting if the goal is a fully sorted array.
Let the active range have length m.
The loop scans each nonpivot element once. There are m - 1 such elements in a nonempty range.
For each scanned element, the procedure performs one comparison:
1A[j] < pivotThe scan performs m - 1 comparisons, which is O(m) comparisons.
A value less than the pivot causes at most one swap during the scan. There can be at most m - 1 qualifying values. After the loop, the procedure performs one final pivot swap.
Movement is also O(m).
The procedure stores:
i,j.These use constant auxiliary storage, so auxiliary space is O(1).
The amount of work does not depend on whether the input happens to be nearly ordered or reversed. Every nonpivot position is scanned once.
Incorrect assumption: Once partition finishes, the entire array is sorted.
Input:
1[3, 1, 4, 2]Partition result:
1[1, 2, 4, 3]The pivot relation is correct:
[1] < 2[4, 3] >= 2But [4, 3] is not sorted.
Correction: Partition is one step of a complete sorting strategy. To sort the full range, sort or recursively partition both sides.
Incorrect assumption or line:
1if A[j] < A[hi]while allowing swaps that can affect the pivot position.
Input:
1[2, 1, 3]If an implementation swaps positions without reserving the pivot position, the value used as the pivot can change during scanning. Later comparisons may use a different value than earlier comparisons.
Wrong state: The procedure no longer compares every scanned value to one fixed pivot value, so the partition relation is not guaranteed.
Correction: Store the pivot value before scanning:
1pivot <- A[hi]Then reserve the pivot cell until the final placement swap.
Incorrect line:
1i <- lo - 1combined with a final swap at i.
Input:
1[5]For the active range [0, 0], this can attempt a swap using index -1.
Wrong state: An invalid array index is used even though a one-element range requires no rearrangement.
Correction: Define the empty less-than region to begin at the range start:
1i <- loAlso return immediately when hi <= lo.
Incorrect line for the procedure’s convention:
1if A[j] <= pivotInput:
1[2, 2, 2]With the required strict less-than rule, the chosen last pivot should end at the left boundary, index 0, and the other equal values should remain to its right.
Using <= instead sends equal values left and produces a different partition convention.
Correction: Use:
1if A[j] < pivotWith this rule, equal values belong to the greater-than-or-equal side.
These inputs follow the same contract:
| Input and pivot choice | Required result |
|---|---|
[] | No partition work for an empty range. |
One-element range such as [5] | No partition work; its only index is returned. |
[2,1], last pivot 1 | [1,2], pivot index 0. |
[1,2,3], last pivot 3 | Earlier values remain left; pivot ends at index 2. |
[2,2,2], last pivot 2 | Chosen pivot ends at index 0; equal values are to its right. |
[-1,3,0,-2], last pivot -2 | Pivot -2 ends at index 0. |
Implement a last-element-pivot partition that:
p,p with a value < pivot,p with a value >= pivot.The executable tests check this partition postcondition and permutation preservation.
1
2def partition_last_pivot(a, lo, hi):
3 if hi <= lo:
4 return lo
5 pivot = a[hi] # store the pivot value before scanning
6 i = lo # next slot for a value < pivot
7 for j in range(lo, hi):
8 if a[j] < pivot: # strict: equal values stay on the right
9 a[i], a[j] = a[j], a[i]
10 i += 1
11 a[i], a[hi] = a[hi], a[i] # put the pivot between the two regions
12 return i
13
14for nums in ([3, 1, 4, 2], [2, 2, 2]):
15 p = partition_last_pivot(nums, 0, len(nums) - 1)
16 print(nums, "pivot index", p)1
2import java.util.Arrays;
3
4public class Main {
5 static int partitionLastPivot(int[] a, int lo, int hi) {
6 if (hi <= lo) return lo;
7 int pivot = a[hi]; // store the pivot value before scanning
8 int i = lo; // next slot for a value < pivot
9 for (int j = lo; j < hi; j++) {
10 if (a[j] < pivot) { // strict: equal values stay on the right
11 int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
12 i++;
13 }
14 }
15 int tmp = a[i]; a[i] = a[hi]; a[hi] = tmp; // put the pivot between the two regions
16 return i;
17 }
18
19 public static void main(String[] args) {
20 int[][] inputs = {{3, 1, 4, 2}, {2, 2, 2}};
21 for (int[] nums : inputs) {
22 int p = partitionLastPivot(nums, 0, nums.length - 1);
23 System.out.println(Arrays.toString(nums) + " pivot index " + p);
24 }
25 }
26}1
2#include <iostream>
3#include <utility>
4#include <vector>
5using namespace std;
6
7int partitionLastPivot(vector<int>& a, int lo, int hi) {
8 if (hi <= lo) return lo;
9 int pivot = a[hi]; // store the pivot value before scanning
10 int i = lo; // next slot for a value < pivot
11 for (int j = lo; j < hi; j++) {
12 if (a[j] < pivot) { // strict: equal values stay on the right
13 swap(a[i], a[j]);
14 i++;
15 }
16 }
17 swap(a[i], a[hi]); // put the pivot between the two regions
18 return i;
19}
20
21int main() {
22 vector<vector<int>> inputs = {{3, 1, 4, 2}, {2, 2, 2}};
23 for (auto& nums : inputs) {
24 int p = partitionLastPivot(nums, 0, (int)nums.size() - 1);
25 cout << "[";
26 for (size_t i = 0; i < nums.size(); i++) cout << (i ? ", " : "") << nums[i];
27 cout << "] pivot index " << p << endl;
28 }
29}1
2function partitionLastPivot(a, lo, hi) {
3 if (hi <= lo) return lo;
4 const pivot = a[hi]; // store the pivot value before scanning
5 let i = lo; // next slot for a value < pivot
6 for (let j = lo; j < hi; j++) {
7 if (a[j] < pivot) { // strict: equal values stay on the right
8 [a[i], a[j]] = [a[j], a[i]];
9 i++;
10 }
11 }
12 [a[i], a[hi]] = [a[hi], a[i]]; // put the pivot between the two regions
13 return i;
14}
15
16for (const nums of [[3, 1, 4, 2], [2, 2, 2]]) {
17 const p = partitionLastPivot(nums, 0, nums.length - 1);
18 console.log(`[${nums.join(', ')}] pivot index ${p}`);
19}Lomuto scans once with a boundary index and puts the pivot in its final slot. Hoare moves two indices toward each other from both ends and swaps out-of-place pairs. Hoare usually swaps less, but it returns a split point, not the pivot's final position.
When every partition leaves one side empty, the range shrinks by one each time. The scans cost n + (n - 1) + ... + 1 comparisons. A last-element pivot does this on sorted and on reverse-sorted input.
Yes. Production versions pick the pivot more carefully, for example at random or as a median of three, and many library sorts are hybrids that switch algorithm when recursion gets too deep.
No. [3, 1, 4, 2] becomes [1, 2, 4, 3]. The pivot 2 is in its final place, but the right side [4, 3] is still unsorted. Quick sort recurses on both sides to finish the job.
With the strict test A[j] < pivot, equal values stay on the right. On [2, 2, 2] no value is smaller, so the pivot swaps to index 0 and the other two 2s sit behind it. Those swaps can reorder equal keys, so it is not stable.