Quicksort with duplicates (3-way) Explained: Tracing [2,2,2,1,2,3]

Imagine you are handed an array that is already sorted, like [1, 2, 3, 4, 5], and your partition strategy always picks the last element as the pivot. In a standard two-way partition, you split the array into two regions: elements less than the pivot and elements greater than or equal to the pivot. Because 5 is already the maximum, every preceding element lands on the left side. Your partition shrinks the problem size by only one element per recursive call, leading to a disastrous $O(n^2)$ time complexity.

Now consider a second scenario where your array is packed with identical values, such as [2, 2, 2, 1, 2, 3] with a pivot of 2. In a traditional two-way scheme, all those duplicate 2s get lumped together with either the smaller or larger partitions. They are treated as distinct recursive burdens, even though they are already in their final relative positions relative to the pivot. You end up wasting precious cycles repeatedly partitioning items that never needed to move.

Without an adaptive strategy, standard Quicksort becomes painfully inefficient when real-world data contains clustered keys, categorical attributes, or pre-sorted segments. We need a way to instantly isolate items equal to the pivot so we can bypass them entirely in future recursive steps.

Standard 2-way partitioning splits an array into two zones around a pivot: elements less than or equal to the left, and elements greater on the right. When applied to our duplicate-heavy working example array $[2,2,2,1,2,3]$ with a pivot of 2, everything equal to the pivot gets shoved arbitrarily into one of those two zones, forcing redundant recursive calls. To solve this, Edsger Dijkstra's Dutch National Flag algorithm introduces a third zone specifically for items equal to the pivot.

The mental model uses four distinct pointers to continuously sweep and categorize an array into four regions during a single pass:

- low: boundary where elements strictly less than the pivot end (everything left of low is $<\text{pivot}$).
- i: current scanning pointer examining the element.
- mid: boundary where elements equal to the pivot end (everything between low and mid is $=\text{pivot}$). Unexamined elements sit between mid and high.
- high: boundary where elements strictly greater than the pivot begin (everything right of high is $>\text{pivot}$)...

[ < pivot | = pivot | unexamined | > pivot ]
^ ^ ^ ^
low mid i high

As our scanning pointer i moves from mid up to high, any element equal to the pivot simply extends the middle zone without triggering further recursive work, directly tackling the $O(n^2)$ trap of redundant elements.

Try this: Given the array [2, 2, 2, 1, 2, 3] with pivot = 2, trace how a 3-way partition would designate the initial regions before scanning starts.

To see why standard Quicksort struggles where 3-way partitioning thrives, we trace two contrasting scenarios from our locked example. First, we examine standard 2-way partitioning on the sorted array [1, 2, 3, 4, 5] using the last element as the pivot. Second, we examine 3-way partitioning on the duplicate-heavy array [2, 2, 2, 1, 2, 3] with pivot 2.

Given

- Scenario A (2-Way): Array [1, 2, 3, 4, 5], pivot = last element.
- Scenario B (3-Way): Array [2, 2, 2, 1, 2, 3], pivot $v=2$, pointers set up via the Dutch National Flag invariant ($lt$, $i$, $gt$).

Scenario A Trace (Standard 2-Way)

1. Pass 1: Pivot is 5. Array is [1, 2, 3, 4, 5]. Elements are scanned; 5 is placed at the end. Subproblem size for the left recursive call is $n-1$ ([1, 2, 3, 4]).
2. Pass 2: Pivot is 4. Subproblem size is $n-2$ ([1, 2, 3]).
3. Pass 3: Pivot is 3. Subproblem size is $n-3$ ([1, 2]).
4. Pass 4: Pivot is 2. Subproblem size is $n-4$ ([1]).

Scenario B Trace (3-Way)

Initial array: [2, 2, 2, 1, 2, 3], pivot $v=2$.
Pointers start at: $lt=0$, $i=0$, $gt=5$.

1. Step 1 ($i=0$): Element at $i$ is 2 (equal to $v$). We increment $i$: $lt=0$, $i=1$, $gt=5$.
2. Step 2 ($i=1$): Element at $i$ is 2 (equal to $v$). We increment $i$: $lt=0$, $i=2$, $gt=5$.
3. Step 3 ($i=2$): Element at $i$ is 2 (equal to $v$). We increment $i$: $lt=0$, $i=3$, $gt=5$.
4. Step 4 ($i=3$): Element at $i$ is 1 (less than $v$). We swap index $i$ with $lt$, then increment both $lt$ and $i$. Array becomes [1, 2, 2, 2, 2, 3], $lt=1$, $i=4$, $gt=5$.
5. Step 5 ($i=4$): Element at $i$ is 2 (equal to $v$). We increment $i$: $lt=1$, $i=5$, $gt=5$.
6. Step 6 ($i=5$): Element at $i$ is 3 (greater than $v$). We swap index $i$ with $gt$, then decrement $gt$. Array becomes [1, 2, 2, 2, 3, 2], $lt=1$, $i=5$, $gt=4$.

Result

- In Scenario A, recursion depth reaches $n$, leading to $O(n^2)$ comparisons because each step only shrinks the array by 1.
- In Scenario B, all duplicate 2s are safely gathered between pointer $lt$ and pointer $gt$. The subsequent recursive calls will only be invoked on the strictly smaller region ([1]) and the strictly larger region ([3, 2] before final normalization), completely bypassing redundant duplicate scans.

Try this: Given the array [2, 2, 2, 1, 2, 3] after Step 4 where array is [1, 2, 2, 2, 2, 3] with lt=1, i=4, gt=5, predict the exact array configuration and pointer values after processing index i=4.

Now it is time to test your mental model against the mechanics of 3-way partitioning. Recall our working array with heavy duplicates: [2, 2, 2, 1, 2, 3]. Suppose we choose a pivot value of 2 and run a single Dutch National Flag partitioning step on an array segment where lt, i, and gt have already advanced partway through the sequence.

Consider the moment when our scan pointer i lands on an element equal to the pivot 2. Based on the rules of 3-way partitioning established in our model, determine exactly how the pointers (lt, i, and gt) and the array elements should shift.

The Task:
Write down or mentally trace the exact invariant conditions for what happens when arr[i] == pivot during a 3-way partition pass. Which pointer advances, which pointer stays put, and which region expands?

- A) lt increments, i increments, gt is untouched
- B) lt stays put, i increments, gt is untouched
- C) lt stays put, i increments, gt decrements
- D) lt increments, i stays put, gt decrements

Try this: Given arr = [2, 2, 2, 1, 2, 3] with pivot = 2.
Trace the pointer updates when arr[i] matches the pivot.

Now that you have mastered how 3-way partitioning groups identical elements into an isolated middle bucket—preventing the $O(n^2)$ collapse seen on our duplicate-heavy array [2, 2, 2, 1, 2, 3]—we can transfer this exact three-way pointer pattern (lt, i, gt) to other data restructuring challenges. The core pattern of maintaining boundary pointers to fan elements into three distinct categories is not just for sorting; it is a universal template for single-pass partitioning.

Consider the classic Dutch National Flag problem, where an array contains only three distinct values representing colors (for example, 0, 1, and 2), and you must sort them in-place in a single pass. By mapping 0 to the < pivot region, 1 to the = pivot region, and 2 to the > pivot region, Dijkstra's 3-way partitioning algorithm solves this exact color-sorting puzzle without any modification to the pointer mechanics we used on [2, 2, 2, 1, 2, 3].

Another powerful transfer is Quicksort with multiple distinct keys or custom multi-criteria sorting where duplicate keys dominate real-world records. When sorting database rows or objects where a primary key or status field frequently repeats, standard 2-way partitioning repeatedly re-processes identical keys, whereas the 3-way approach bounds the recursion strictly to elements strictly less than and strictly greater than the pivot.

To test your transfer capability, consider how you would adapt this logic if your array contained four distinct categories instead of three. While a 3-way partition uses four pointers (low, lt, i, gt, high), scaling to $k$ categories requires maintaining $k-1$ boundary pointers to manage each distinct category in a single linear sweep.

Suppose you are given an array containing only three distinct integer values: 0, 1, and 2, representing red, white, and blue elements respectively. Explain how the pointer mechanics of 3-way partitioning (using pointers lt, i, and gt) sort this array in a single pass of $O(n)$ time, and state which regions each pointer bounds.