Sort Colours Through an API
An array of n colours (0, 1, 2) is hidden behind an API: api.getColor(i) returns the colour at index i, and api.swap(i, j) exchanges two positions. Sort the array in place so that all 0s come first, then 1s, then 2s, using only those two calls, in one pass and without counting first.
hidden [2, 0, 2, 1, 1, 0] -> after sortColors(6, api): [0, 0, 1, 1, 2, 2]
The grader reads the array back afterwards and fails a run that reads more than 2n colours.
Hints
Hint 1
Three regions: 0s before low, 2s after high, unknown between mid and high. Inspect mid: a 0 swaps to low and both advance; a 2 swaps to high and only high shrinks; a 1 just advances mid.
Hint 2
Do not advance mid after swapping with high — the value that arrived is still unknown.