3-Way Quick Sort

Divide and Conquer

Recursively breaks the problem into smaller sub-problems, solves them, and combines the results.

Exchange

Sorts by repeatedly swapping adjacent elements to move them to their correct positions.

Adaptive

Performance improves significantly on data that is already partially sorted.

In-Place

Requires a constant amount of extra memory space (O(1)), regardless of input size.

Unstable

Does not guarantee the relative order of elements with equal values.

Dutch national flag partitioning groups all pivot-equal values in one pass. Recursion skips the equal group, which helps duplicate-heavy inputs.

Visualize Fullscreen

Demo

20 elements • 4x Speed

No Data

Did you know?

If every value equals the pivot, the equal region consumes the whole input in one partition pass.
Its three moving regions echo the Dutch national flag problem: less than, equal to, and greater than the pivot.
This version reads the middle value as its pivot without first moving it to an edge. After the scan, every pivot-equal element occupies the central region and is excluded from later recursive calls.

How it Works

Choose a pivot from the current range.
Keep three regions: smaller, equal, and larger values.
Recurse only on the smaller and larger regions.

Complexity Analysis

Best Case

O(n)

Average

O(n \log n)

Worst Case

O(n^2)

Space

O(n)

Advantages

Handles many duplicate keys efficiently.
Uses constant partition storage.

Disadvantages

Unstable.
A poor pivot can still cause quadratic work.

Implementation

JavaScript 3-way-quick-sort.js

function threeWayQuickSort(a) {
  function sort(lo, hi) {
    if (lo >= hi) return;
    const pivot = a[lo + Math.floor((hi - lo) / 2)];
    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++;
    }
    sort(lo, lt - 1); sort(gt + 1, hi);
  }
  sort(0, a.length - 1); return a;
}