Three-Way Quick Sort

Partition values into less-than, equal-to, and greater-than regions so duplicate pivots finish together.

Core idea

Maintain three regions around one pivot: values below it, values equal to it, and values above it. A single scan expands the regions until no unknown values remain.

Read the visualization

The lt, i, and gt pointers bound the three colored regions. Less and greater branches swap values across a boundary, while equal values simply advance the scan.

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 explicit work stack.

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

stack deep0

lo0

hi7

pivot-

lt-

gt-

1 / 36

Complexity and tradeoffs

Time: Average O(n log n); worst O(n^2). Space: Average O(log n). Three-way partitioning is especially effective when many input values are equal.

Invariant: Before every comparison, positions before lt are smaller, positions from lt to i are equal, and positions after gt are greater than the pivot.

Where it fits

Three-way partitioning is the preferred Quick Sort variant for data with many duplicate keys. Distinct random data behaves similarly to ordinary Quick Sort.

Algorithm Visualizer

Three-Way Quick Sort

Core idea

Read the visualization

Complexity and tradeoffs

Where it fits