Three-Way Partition — Duplicates Around a Pivot

Three-way partition (beyond Dutch flag on {0,1,2}) generalizes quicksort when many elements equal the pivot. It groups <, =, > regions so recursion skips the middle—critical on duplicate-heavy inputs.

Why this shows up in the real world

Log deduplication pipelines may partition log lines by hash bucket <, =, > pivot analogously when bucketing by severity code with massive ties. Database index builds on low-cardinality columns face many equal keys—three-way thinking reduces recursion depth. Competitive programming problems with arrays of only a few distinct values map here.

Core idea (explained for students)

Track lt and gt boundaries while scanning with i: elements < pivot swap to the left region; > pivot swap to right; == pivot stay in the middle by careful swaps. After one pass, recurse only on < and > subarrays. Expected time improves dramatically when duplicates dominate.

Try this in Python

# Simplified 3-value partition story using Dutch flag core
from collections import Counter

def bucket_counts(nums):
    return Counter(nums)

print(bucket_counts([2, 0, 2, 1, 0, 1, 2]))

Common mistakes

• Infinite loops if i not advanced correctly on swaps.
• Confusing three-way partition with full Dutch flag for arbitrary many colors.
• Forgetting to move pivot range between recursive calls.

Key takeaways

• Essential for duplicate-heavy quicksort.
• Same spirit as Dutch national flag.
• Pair with random pivot for robustness.