Sort an Array of 0s, 1s, and 2s (Dutch National Flag)

You are given an array that contains only the integers 0, 1, and 2, representing three categories. Rearrange the array in-place so that all the 0s appear first, followed by all the 1s, and then all the 2s. The relative order within each category does not matter, only the final grouping.

Input: The first line contains a single integer n, the size of the array. The second line contains n space-separated integers, each equal to 0, 1, or 2. Output: Print the sorted array as n space-separated integers on a single line.

1 <= n <= 8000 arr[i] is one of {0, 1, 2}

This is the canonical 'Dutch National Flag' algorithm (named after the Dutch flag's three horizontal bands) - recognizing this name signals familiarity with a well-known pattern that generalizes to any three-way partitioning problem.

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

1. Keep three pointers: 'low' (boundary for the next 0), 'mid' (the element currently being examined), and 'high' (boundary for the next 2). 2. If arr[mid] is 0, swap it to the low boundary and advance both low and mid. 3. If arr[mid] is 1, just advance mid. If arr[mid] is 2, swap it to the high boundary and shrink high - but DON'T advance mid yet, since the swapped-in value hasn't been examined.

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

The array may already be sorted, may contain only one distinct value, or may have all three values already grouped in contiguous blocks in reverse order.

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 still needs to be examined on the very next iteration.