Dutch national flag problem - performance in Python and C (two pivot partition, three way partition)

Dutch national flag problem - performance in Python and C (two pivot partition, three way partition)

One of the typical interview questions is the three way partitioning, also known as the Dutch national flag problem: given an array with three different values, sort it in a way that all values are grouped together (like a three colored flag) in linear time without extra memory. The problem was first described by Edsger Dijkstra.

As it's a typical sorting problem, any sorting would do but they would need n*log(n) time. There are two good solutions to it: do a counting sort which requires two passes over the array; place the elements to their correct location using two pointers.

Read full article from Dutch national flag problem - performance in Python and C (two pivot partition, three way partition)