Dutch National Flag: In-Place 3-Way Partitioning

Dijkstra's Dutch National Flag algorithm partitions an array into three buckets (e.g. 0s, 1s, 2s or < pivot, == pivot, > pivot) in-place in a single pass with 3 pointers (low, mid, high).

function sortColors(nums: number[]): void {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;

  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--; // mid pointer stays to evaluate swapped item
    }
  }
}