Sort an Array of 0s, 1s, and 2s

Problem Given an array containing only the values 0, 1 and 2, sort it in ascending order in place in a single pass — no counting pass followed by an overwrite pass, and no library sort.

Input / Output

• Input: array arr of length n, every element in {0, 1, 2}.
• Output: the same array mutated so all 0s precede all 1s, which precede all 2s.

Constraints

• In place: O(1) extra space.
• Single pass: each element inspected a constant number of times, O(n) total.
• Array may be empty, or contain only one of the three values.

Example

• [2,0,1,2,1,0] → [0,0,1,1,2,2]
• Tricky case: [2,2,2,0,0,0] — every element must cross the whole array.