Dijskstra's three-way partitioning is useful in quick sort dealing with duplicates in array. Conceptually this method keeps two pointers that group elements equal to pivot. (if lt <= i <= gt, then A[i] == pivot)

```
public class Solution {
// version: Dijskstra's three-way partitioning
public void sortColors(int[] A) {
int n = A.length;
if (n < 2) return;
int lt = 0;
int gt = n - 1;
int i = 0;
while (i <= gt) {
// #1 is the pivot
if (A[i] < 1) exch(A, i++, lt++);
else if (A[i] > 1) exch(A, i, gt--);
else i++;
}
}
private void exch(int[] A, int p, int q) {
int temp = A[p];
A[p] = A[q];
A[q] = temp;
}
}
```