The Dutch National flag problem

**(In python)**A famous problem given by Edsgar Dijkstra is to sort an array of red, white and blue symbols (pebbles in the original statement) so that all reds come together, followed by all whites, followed finally by all blues; its called the Dutch National Flag problem because the Dutch flag consists of three stripes with red at the top, blue at the bottom, and white in the middle.

You are allowed to scan through the array only once, meaning it has a runtime of O(n),and the only operations permitted are to examine the color of the symbol at a given array location and to swap the symbols at two locations. Show proof that this algorithm functions correctly and give its runtime analysis