dutch national flag problem
Initially all array values are treated as unpartitioned:
[unpartitioned values]
Array split into four parts as the iteration proceeds:
[ values < mid | values = mid | unpartitioned values | values > mid ]
procedure three-way-partition(A : array of values, mid : value):
i ← 0
j ← 0
k ← size of A - 1
while j <= k:
if A[j] < mid:
swap A[i] and A[j]
i ← i + 1
j ← j + 1
else if A[j] > mid:
swap A[j] and A[k]
k ← k - 1
else:
j ← j + 1