Three-Colour Sort

A tray holds tokens of three colours, written as numbers: 0 for red, 1 for white and 2 for blue. Write sort_colours(tokens) that rearranges the list tokens in place so that all the 0s come first, then all the 1s, then all the 2s, and returns that same list.

Try to do it in one pass over the list, swapping tokens as you go, without counting them first and without calling sort.

Examples

sort_colours([2, 0, 1, 2, 0])   # returns [0, 0, 1, 2, 2]
sort_colours([1, 1, 0])         # returns [0, 1, 1]
sort_colours([2, 2, 2])         # returns [2, 2, 2]

Constraints

• 0 <= len(tokens) <= 100,000
• Every token is 0, 1 or 2

Note

The tests look at the list you were given as well as the value you return, so change tokens itself rather than building a new list.