Three-Way Quick Sort Visual Guide | Draftsbook

Divide & Conquer · Article 12 of 62

Three-Way Quick Sort

Partition into three regions — less than, equal to, and greater than the pivot — so duplicates are sorted by being touched only once.

How it works

Standard Quick Sort partitions into "≤ pivot" and "> pivot". On data with many duplicates, equal elements get repeatedly compared and shuffled even though they're already in their right neighborhood.

Three-Way Quick Sort, attributed to Dijkstra (the "Dutch National Flag" partition), maintains three pointers and partitions into:

arr[lo..lt-1] — strictly less than pivot.
arr[lt..gt] — equal to pivot.
arr[gt+1..hi] — strictly greater than pivot.

The middle region is already sorted by definition, so recursion happens only on the two outer regions. On input with k distinct values, this gives O(n log k) runtime instead of O(n log n).

Complexity

Best time

O(n)

Average time

O(n log n)

Worst time

O(n²)

Extra space

O(log n)

Stable

In-place

Yes

Try the Few unique preset and watch the equal-region carve out a giant pivot-coloured block on the very first partition — that whole block is done in one pass.

Interactive visualization

Pseudocode

procedure threeWayQuickSort(A, lo, hi):
  if hi ≤ lo: return
  pivot ← A[lo]
  lt ← lo; gt ← hi; i ← lo + 1
  while i ≤ gt:
    if   A[i] < pivot: swap A[i++], A[lt++]
    elif A[i] > pivot: swap A[i],  A[gt--]
    else:               i++
  threeWayQuickSort(A, lo, lt − 1)
  threeWayQuickSort(A, gt + 1, hi)

JavaScript implementation

function threeWayQuickSort(arr, lo = 0, hi = arr.length - 1) {
  if (hi <= lo) return arr;
  const pivot = arr[lo];
  let lt = lo, gt = hi, i = lo + 1;
  while (i <= gt) {
    if (arr[i] < pivot) { [arr[i], arr[lt]] = [arr[lt], arr[i]]; i++; lt++; }
    else if (arr[i] > pivot) { [arr[i], arr[gt]] = [arr[gt], arr[i]]; gt--; }
    else i++;
  }
  threeWayQuickSort(arr, lo, lt - 1);
  threeWayQuickSort(arr, gt + 1, hi);
  return arr;
}

Pros and cons

Pros

O(n log k) for k distinct keys — best case linear on highly-duplicate data.
Eliminates redundant comparisons on equal keys.
Still in-place with O(log n) stack.
Easy to combine with randomization.

Cons

Slightly more work per partition than 2-way — slower on all-distinct keys.
Not stable.
Still O(n²) worst case without randomization.

When to use it

Data with many duplicates: categorical columns, IPs, timestamps clipped to minute, low-cardinality keys.
Java's Arrays.sort uses a variant of 3-way quicksort.
Frequency-bucketed processing where ties cluster.

Up next: Dual-Pivot Quick Sort — leaving the partition family entirely — building a max-heap and repeatedly extracting the top.

Three-Way Quick Sort: Mechanism, Complexity Analysis & Interactive Visualizer