Dutch Flag Problem

For an array containing 0, 1, and 2, keep three regions: [0, low) contains only 0s, [low, mid) contains only 1s, (high, n-1] contains only 2s, and [mid, high] is unclassified. Inspect a[mid]. If it is 0, swap it with a[low], increment both low and mid. If it is 1, increment mid. If it is 2, swap with a[high] and decrement high, but do not increment mid because the incoming value has not been classified. This invariant proves each element is processed safely in one pass. A counting solution is also O(n) but makes another pass and may not satisfy an in-place requirement. Test an empty array, all one color, alternating colors, and a 2 at mid followed by a 0. The algorithm takes O(n) time and O(1) additional space.