The Dutch National Flag Problem

The Dutch National Flag algorithm lets you arrange/sort a list in O(n) time and O(1) space given the elements of the list are limited to being one of three unique values.

Algorithm Steps:
1. Initialise low and mid pointing to the first element of the list, and high pointing to the last element. Let middle be the middle element of the three values.
2. While mid is less than or equal to high:
2a. If nums[mid] == middle, increment mid.
2b. If nums[mid] is greater than middle, swap nums[mid] and nums[high] and decrement high.
2c. If nums[mid] is less than middle, swap nums[mid] and nums[low] and increment both low and mid.

Видео The Dutch National Flag Problem канала emcapsulation