Dual-Pivot Quick Sort

Choose two pivots and partition one interval into three regions during a single scan.

Core idea

Order two endpoint pivots p and q, then divide the scan into values below p, between p and q, and above q. Placing both pivots finishes three subproblems at once.

Read the visualization

Two pivot markers remain visible while lt, i, and gt move the unknown region inward. Each comparison selects one of the three partition branches.

Input

Interval stack: each frame is a pending subarray a[lo..hi]

Stack empty: every position is final

Take the next unsorted interval from the work stack.

1function dualPivotQuickSort(a: number[]): number[] {
const stack: [number, number][] = [[0, a.length - 1]];
while (stack.length > 0) {
  const [lo, hi] = stack.pop()!;
  if (a[lo] > a[hi]) [a[lo], a[hi]] = [a[hi], a[lo]];
  const p = a[lo], q = a[hi];
  let lt = lo + 1, i = lo + 1, gt = hi - 1;
  while (i <= gt) {
    if (a[i] < p) {
      [a[lt], a[i]] = [a[i], a[lt]];
      lt++; i++;
    } else if (a[i] > q) {
      [a[i], a[gt]] = [a[gt], a[i]];
      gt--;
    } else {
      i++;
    }
  }
  lt--; gt++;
  [a[lo], a[lt]] = [a[lt], a[lo]];
  [a[hi], a[gt]] = [a[gt], a[hi]];
  if (hi > gt + 1) stack.push([gt + 1, hi]);
  if (gt - 1 > lt + 1) stack.push([lt + 1, gt - 1]);
  if (lt - 1 > lo) stack.push([lo, lt - 1]);
}
return a;
27}

stack deep0

lo0

hi7

lt-

gt-

1 / 27

Complexity and tradeoffs

Time: Average O(n log n); worst O(n^2). Space: Average O(log n). Good partitions reduce recursion depth and can improve cache behavior, but the worst case remains quadratic.

Invariant: The outer regions are already classified relative to p and q, and only the interval between i and gt remains unknown.

Where it fits

Dual-pivot partitioning can reduce comparisons and improve cache behavior in tuned primitive-array sorts. Pivot selection remains essential to avoid unbalanced recursion.

Algorithm Visualizer

Dual-Pivot Quick Sort

Core idea

Read the visualization

Complexity and tradeoffs

Where it fits