Dual-Pivot Quick Sort Visual Guide | Draftsbook

Divide & Conquer · Article 13 of 62

Dual-Pivot Quick Sort

Two pivots, three partitions. Vladimir Yaroslavskiy's 2009 variant became the default sort in Java 7 and runs about 10–20% faster than classical quicksort.

How it works

Dual-Pivot Quick Sort picks two pivots p ≤ q and partitions into:

< p
p ≤ x ≤ q
> q

The recursion then descends into three sub-ranges, each smaller on average than a single split would produce. The number of comparisons per pass is slightly higher, but the recursion tree is shallower, and modern CPUs love the branch pattern.

Why it became Java's default: empirical wins on real-world numeric data, predictable behavior, and a clean integration with insertion-sort fallbacks at small sizes.

Complexity

Best time

O(n log n)

Average time

O(n log n)

Worst time

O(n²)

Extra space

O(log n)

Stable

In-place

Yes

Java's Arrays.sort for primitive arrays uses dual-pivot quicksort with insertion-sort cutoff and adaptive runs. Most reference benchmarks favor it over classical quicksort.

Interactive visualization

Pseudocode

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

JavaScript implementation

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

Pros and cons

Pros

Faster than classical quicksort on real numeric data (≈10–20%).
Three-way recursion — slightly shallower trees on average.
Adopted as Java 7+ default for primitives.
Cache and branch-prediction friendly.

Cons

More code and more edge cases than classical quicksort.
Still O(n²) worst case unless paired with randomization or median selection.
Not stable.

When to use it

Default in-memory primitive sort in Java and many modern libraries.
Numerical data processing pipelines.
Hot path in databases that need both speed and small code.

That is the final algorithm in the series — see the project index.md for the full roster.

Dual-Pivot Quick Sort: Mechanism, Complexity Analysis & Interactive Visualizer