Challenge: The Dutch National Flag Problem

Problem statement

Implement a function that sorts an array of $0$s, $1$s, and $2$s. This is called the Dutch National Flag problem. Since the number 0 can be represented by blue, 1 by white, and 2 by red, the task is to transform the array input into the Dutch flag.

Note: Try solving this problem in-place and in linear time without using any extra space.

Input

An array of 0s, 1s, and 2s.

Output

An array where the numbers 0, 1, and 2 are sorted.

Sample input

arr = {2, 0, 0, 1, 2, 1, 0};

Sample output

result = {0, 0, 0, 1, 1, 2, 2}