Sort an Array of Three Colors

You are given an array of n integers, each either 0, 1, or 2, representing three categories (for example red, white, and blue). Sort the array in place so that all 0s come first, followed by all 1s, followed by all 2s, using a single-pass three-way partition rather than a general-purpose sort.

Input: The first line contains the integer n. The second line contains n space-separated integers, each 0, 1, or 2. Output: Print the n sorted values, space-separated, on a single line.

1 <= n <= 10^5 arr[i] is one of 0, 1, or 2

This is the array-category twin of the identically-solved Sorting-category problem 'Sort an Array of 0s, 1s, and 2s (Dutch National Flag)' - the exact same three-pointer technique, just filed under the Two Pointer category here since it's fundamentally a multi-pointer partitioning technique.

Sort an array of 0s, 1s, and 2s in a single pass using a three-way partition (the Dutch National Flag algorithm). Brute force: Run a general-purpose comparison-based sort directly - this costs O(n log n), wasteful when there are genuinely only 3 distinct values to deal with. Optimised: The three-pointer Dutch National Flag partition classifies each element into exactly one of 3 buckets in a SINGLE linear pass with O(1) extra space - no comparisons between arbitrary values are ever needed, just direct classification based on the value being exactly 0, 1, or 2.

1. Maintain THREE pointers: 'low' marking the boundary after the last 0, 'mid' scanning the array, and 'high' marking the boundary before the first known 2. 2. When arr[mid] is 0, swap it with arr[low] and advance BOTH low and mid; when it's 2, swap it with arr[high] and move high back WITHOUT advancing mid (the swapped-in value hasn't been examined yet). 3. When arr[mid] is 1, it's already in the right region, so just advance mid; stop once mid passes high.

Time: O(n) - a single pass through the array. Space: O(1) - the partitioning happens entirely in place.

Handle an array containing only one distinct value (e.g. all 2s) and the largest n = 10^5; a correct approach uses a single O(n) pass with three pointers rather than a library sort.

Be ready to explain precisely why the mid pointer does NOT advance after a '2'-swap - the value swapped in from the high boundary hasn't been classified yet and must be examined on the very next iteration.