What is DNF sort?

DNF sort, short for “Dutch National Flag sort,” is a sorting algorithm designed to segregate elements of an array into three distinct groups based on a specific condition. It was developed by Edsger Dijkstra, a Dutch computer scientist, and is particularly useful for sorting elements that have three possible values or categories.

In DNF sort, the array is partitioned into three sections:

1. Elements less than a given value (e.g., 0)
2. Elements equal to the given value
3. Elements greater than the given value (e.g., 2)

The algorithm works by maintaining three pointers: one for the current element being processed, one for the boundary of elements less than the given value, and one for the boundary of elements greater than the given value. As the algorithm iterates through the array, it swaps elements to move them into their respective categories until the entire array is sorted.

DNF sort is particularly efficient for sorting arrays with a limited number of distinct values, such as binary arrays (0s and 1s) or arrays with small integer values. It has a time complexity of O(n), making it a linear time sorting algorithm.

The task is to randomly arrange balls of white, red, and blue in such a way that balls of the same color are placed together. For DNF (Dutch National Flag), we sort an array of 0, 1, and 2’s in linear time that does not consume any extra space.