Course contentsShow
← Computer Science
Lesson 772 of 2,87218. Sorting AlgorithmsFree lesson

Three-Way Partitioning for Duplicate Keys

Handle arrays with many duplicate values efficiently using three-way partitioning into less, equal, greater.

Three-Way Partitioning for Duplicate Keys

What you'll learn: How to make Quicksort dramatically faster when your array contains many repeated values.

The Problem with Standard Quicksort

When you have an array with many duplicate values (like [5, 2, 5, 5, 1, 5, 3, 5]), standard Quicksort wastes time. If you pick 5 as your pivot, the partition operation puts all 5s on one side, creating unbalanced partitions. You end up recursing on elements you already know are equal to the pivot—unnecessary work!

The Three-Way Solution

Instead of dividing the array into two regions (less than pivot, greater-or-equal to pivot), three-way partitioning creates three regions:

  1. Less than pivot (elements < pivot)
  2. Equal to pivot (elements == pivot)
  3. Greater than pivot (elements > pivot)

Think of it like sorting colored balls: red (less), white (equal), blue (greater). Once you've grouped all the white balls together, you never need to touch them again!

How It Works

Three-way partitioning uses two boundaries instead of one:

  • Elements before the first boundary are less than the pivot
  • Elements between boundaries equal the pivot
  • Elements after the second boundary are greater than the pivot

After partitioning, you only recurse on the less-than and greater-than sections. All equal elements are already in their final position.

The Payoff

For arrays with many duplicates, this transforms Quicksort from O(n²) worst-case to O(n) in the best case (when all elements are identical). Average performance improves dramatically when duplicates are common.

Key Takeaway: Three-way partitioning splits arrays into less-than, equal-to, and greater-than regions, allowing Quicksort to skip sorting duplicate values entirely—essential for real-world data with repeated elements.