The Dutch Flag Sort

The Dutch Flag Partition

Sorting usually requires hundreds of comparisons, but what if you only have three types of items (like the Red, White, and Blue of the Dutch Flag)? By using three pointers (low, mid, and high), you can literally "push" each item into its correct zone (0s to the left, 2s to the right, and 1s in the middle) in a single physical pass through the array.

The Assignment

Your mission is to partition the colors (0, 1, and 2). Your function receives an array nums.

1. Initialize low and mid at index 0, and high at the last index.
2. While the mid pointer has not passed the high pointer:
   • If the value at mid is 0: Swap it with low, and move both pointers forward.
   • If the value at mid is 1: Simply move the mid pointer forward.
   • If the value at mid is 2: Swap it with high, and move the high pointer backward.
3. Print every number in the now-partitioned array on a new line.