Dutch National Flag Algorithm

#programming #algorithms

A sorting algorithm designed for sorting an array that has only three unique entries.

Generally modeled as $0,1,2$ are the inputs.

The goal is to sort it faster than traditional sorting algorithms that use $O(n\log n)$ time.

The method is to maintain a low, mid and high pointers.

The low and high pointers maintain the boundary for the lowest and highest value observation, $0$ and $2$, respectively.

The mid pointer traverses the list and swaps element

• If $0$, swap with low, increment both low and mid
• If $2$, swap with high, increment mid, decrement high.
• If $1$, Do nothing.

It achieves a time complexity of $O(n)$, the theoretical limit for a sorting algorithm (since you have to see every element atleast once).

A modified version is used in Quicksort with huge datasets that often involve multiple duplicate keys.