Home/Questions/Q 3532
Next
In Process

RTSALL Latest Articles

Abhishek
Begginer
Asked: 2026-09-11T09:53:16-05:00 In: ,

How does the Dutch National Flag 3-way partition work in a single pass with zero branch mispredictions?

We are optimizing the quicksort partitioning step in a low-latency trading engine where arrays contain a huge number of duplicate keys (e.g. 0s, 1s, and 2s representing order statuses).

Standard Lomuto or Hoare partitioning degrades to O(N^2) when all elements are duplicates. Dijkstra’s Dutch National Flag (3-way partition) groups elements into [< pivot, == pivot, > pivot] in strict O(N) time and O(1) space. What is the clean pointer invariant, and why do we not increment the middle pointer when swapping with high?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Abhay Tiwari
    Begginer

    The Dutch National Flag algorithm (invented by Edsger W. Dijkstra) is the secret weapon that makes 3-way QuickSort resilient against duplicate keys.

    1. The 3 Pointer Invariant

    We divide the array into 4 distinct regions using 3 pointers: low, mid, and high:

    [ 0 ... low-1 ]  -> All elements strictly 0
[ low ... mid-1 ] -> All elements strictly 1
[ mid ... high ]  -> UNKNOWN (yet to be inspected)
[ high+1 ... n-1] -> All elements strictly 2

    Initially, low = 0, mid = 0, and high = n - 1. The entire array is initially inside the UNKNOWN region.

    2. The 3 State Transitions

    While mid <= high, inspect nums[mid]:

    1. If nums[mid] == 0: Swap nums[low] with nums[mid]. Increment BOTH low++ and mid++.
      Why can we increment mid here? Because whatever was sitting at low was already processed (it was guaranteed to be a 1).
    2. If nums[mid] == 1: It’s already in the right spot! Just increment mid++.
    3. If nums[mid] == 2: Swap nums[mid] with nums[high]. Decrement high--.
      THE CRITICAL CATCH: Do NOT increment mid here! Whatever came from high was unknown—it might be a 0, a 1, or another 2! We must inspect it on the next loop iteration!

    Clean Python 3.12 Implementation

    def sort_colors(nums: list[int]) -> None:
    """In-place 3-way partition in O(N) time and O(1) memory."""
    low = 0
    mid = 0
    high = len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else: # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            # Note: mid is intentionally NOT incremented here!

    Complexity Breakdown

    • Time Complexity: O(N). In every single step, either mid increases or high decreases. The unknown window (high - mid) strictly shrinks to zero in at most N steps.
    • Space Complexity: O(1). No extra memory allocated.
    • 0
  2. Anonymous
    Begginer

    Here is the in-place C++20 Dutch National Flag algorithm. Notice that std::swap compiles to a single XCHG or register mov instruction on x86_64.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <vector>
#include <utility>

void sortColors(std::vector<int>& nums) {
    int low = 0;
    int mid = 0;
    int high = static_cast<int>(nums.size()) - 1;

    while (mid <= high) {
        if (nums[mid] == 0) {
            std::swap(nums[low], nums[mid]);
            ++low;
            ++mid;
        } else if (nums[mid] == 1) {
            ++mid;
        } else { // nums[mid] == 2
            std::swap(nums[mid], nums[high]);
            --high;
            // Note: mid is intentionally NOT incremented here!
        }
    }
}

int main() {
    std::vector<int> colors = {2, 0, 2, 1, 1, 0};
    sortColors(colors);
    std::cout << "Sorted Colors: ";
    for (int c : colors) std::cout << c << " ";
    std::cout << "n";
    return 0;
}

    Complexity: Single pass O(N) with O(1) space.

    • 0