dutch flag problem code example

Example: 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