## What is it? Sort an array containing only 0s, 1s, and 2s in-place in a single pass without counting. Also known as the Dutch National Flag algorithm (by Dijkstra). ## How it works - Three pointers: `low = 0` (boundary for 0s), `mid = 0` (current), `high = n-1` (boundary for 2s) - While `mid <= high`: - `arr[mid] == 0` → swap `arr[low]` and `arr[mid]`; advance `low++`, `mid++` - `arr[mid] == 1` → already in place; advance `mid++` - `arr[mid] == 2` → swap `arr[mid]` and `arr[high]`; `high--` (do NOT advance `mid` — the swapped element needs checking) ## When to use - Sorting 3-valued arrays in one pass - Generalized: k-way partition (extend with k pointers) - Quicksort partition step (three-way partition for equal elements) ## Key Points - O(n) time, O(1) space — single pass - Do not increment `mid` after swapping with `high`, because the swapped element is unseen - After the loop: [0..low-1] = 0s, [low..mid-1] = 1s, [high+1..n-1] = 2s