Dutch National Flag Algorithm. Explained with playing cards.

Dutch National Flag AKA DNF is a well-known algorithmic problem for coding interviews. It was first proposed by
Edgar Djaikstra, one of the brightest minds in the history of computer science who happens to be Dutch by nationality. The flag of the Netherlands consists of three colors: white, red, and blue. Our objective is to group the colors together and maintain the correct order. In other words, this is a sorting problem of 3 unique values. For example, sorting an array consisting only 0, 1, and 2’s. Or it could be 3 unique ranges of values. For example - values less than pivot equals to pivot and greater than the pivot. ( We need this type of sorting in quicksort). The idea of this algorithm is to push low values to the left, high values to the right, and don’t care about the mid values, it will be in the middle eventually.
We will use three pointers - low, mid, high and will keep 4 invariants.
- Everything at the left of low is low values.
- From the low pointer to the left of the mid pointer are mid values.
- From mid pointer to the high pointer are unknown values.
- Everything at the right of the high pointer has high values.