Dual-Pivot 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.

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.

The outer values become ordered pivots. A single scan groups values below the first pivot, between pivots, and above the second; each group is recursively sorted.

Visualize Fullscreen

Demo

20 elements • 4x Speed

No Data

Did you know?

Two pivots create three partitions and can both reach their final positions after one partition pass.
OpenJDK uses a highly optimized dual-pivot Quicksort for primitive arrays; the visual version here uses a simpler partition.
If the two selected pivots have the same value, this implementation skips sorting the middle region. Values outside that equal-pivot block still receive recursive calls on the left and right.

How it Works

Order two pivots at the ends of the range.
Scan and move values into three partitions.
Put pivots in their final positions and sort each partition.

Complexity Analysis

Best Case

O(n \log n)

Average

O(n \log n)

Worst Case

O(n^2)

Space

O(n)

Advantages

Partitions into three regions in one scan.
Uses in-place swaps.

Disadvantages

Unstable.
Worst case is quadratic without pivot safeguards.

Implementation

JavaScript dual-pivot-quick-sort.js

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