Sort array of 0,1,2

Given an array of 0s, 1s and 2s only in a mixed fashion. The task is to seperate out them such that 0s are on the left, 1s in the middle, and 2s on the right. The algorithm should run in linear time.

This problem is called "Dutch National Flag". There are lot of puzzles asked in the interview based on this.

Solution