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

Given an array containing only the values 0, 1 and 2, sort it without using a general-purpose sorting algorithm (count occurrences or use the Dutch National Flag partition). Print the sorted array.

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

1 <= n <= 10^5

The mid pointer only advances after a '1' or after a '0'-swap, but NOT after a '2'-swap - since the value swapped in from the high boundary hasn't been classified yet and still needs to be examined on the next iteration.

Sort an array that contains only three possible values (0, 1, 2) without using a general-purpose sort. Brute force: Run a standard comparison-based sort (like quicksort or merge sort) - this technically works but costs O(n log n), wasteful when there are genuinely only 3 distinct values to deal with. Optimised: Since there are only 3 possible values, either counting each value's frequency and rebuilding the array, or the elegant three-pointer 'Dutch National Flag' partition, sorts the array in a SINGLE linear pass - no comparisons between arbitrary values needed at all, just bucket classification.

Sort the array using a standard general-purpose comparison sort (for example the language's built-in sort function). This trivially produces a correctly ordered array since 0, 1, 2 sort the same way any values would, but it ignores that only three distinct values are involved, does more comparison work than necessary, and does not satisfy this problem's specific requirement to avoid a general-purpose sort. Time: O(n log n) Space: O(log n) to O(n) depending on the sort implementation

Make one pass through the array counting how many 0s, 1s, and 2s appear, then make a second pass overwriting the array positions with that many 0s, followed by that many 1s, followed by that many 2s. Since the value domain is fixed to just three values, counting occurrences and rewriting the array directly is enough to sort it, and this avoids any element-to-element comparisons entirely, running in linear time with just two passes. Time: O(n) Space: O(1)

Maintain three pointers: low and mid starting at the beginning and high starting at the end. Look at arr[mid]: if it's 0, swap it with arr[low] and advance both low and mid; if it's 1, just advance mid; if it's 2, swap it with arr[high] and decrease high without advancing mid (since the swapped-in value from the end still needs to be examined). Continue until mid passes high. This sorts the array in a single pass using only swaps, avoiding the second overwrite pass that counting sort needs. Time: O(n) Space: O(1)

1. Keep three pointers: 'low' (boundary for the next 0), 'mid' (current element being examined), and 'high' (boundary for the next 2), all working within one single pass. 2. If the element at mid is 0, swap it to the low boundary, and advance both low and mid. 3. If the element at mid is 1, it's already in the right general zone, just advance mid. 4. If the element at mid is 2, swap it to the high boundary and shrink high - but don't advance mid yet, since the swapped-in value still needs to be examined.

Time: O(n) - a single pass through the array, regardless of which of the two approaches you use. Space: O(1) for the three-pointer in-place approach; O(1) extra (beyond output) for the counting approach too, since you only need 3 counters.

n = 1 (already trivially sorted); an array containing only one distinct value among 0, 1, 2; and n = 10^5 (largest, confirming the counting or Dutch-flag approach is a single O(n) pass).

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