Dual Pivot Quicksort

Dual pivot quicksort extends quicksort by using two pivots instead of one. It partitions the array into three regions in a single pass:

elements less than the first pivot
elements between the two pivots
elements greater than the second pivot

This approach reduces comparisons in practice and improves performance on modern hardware.

It is used in standard library implementations such as Java for primitive arrays.

Problem

Given an array $A$ of length $n$ , reorder it such that:

A[0] \le A[1] \le \dots \le A[n-1]

Idea

Choose two pivots $p$ and $q$ such that:

p \le q

Partition the array into three regions:

[ < p ;|; p \le x \le q ;|; > q ]

Then recursively sort the three regions.

Algorithm

dual_pivot_quicksort(A, lo, hi):
    if lo >= hi:
        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]
            lt += 1
        else if A[i] > q:
            while A[gt] > q and i < gt:
                gt -= 1
            swap A[i], A[gt]
            gt -= 1
            if A[i] < p:
                swap A[i], A[lt]
                lt += 1
        i += 1

    lt -= 1
    gt += 1

    swap A[lo], A[lt]
    swap A[hi], A[gt]

    dual_pivot_quicksort(A, lo, lt - 1)
    dual_pivot_quicksort(A, lt + 1, gt - 1)
    dual_pivot_quicksort(A, gt + 1, hi)

Example

Let:

A = [9, 3, 7, 1, 8, 2, 5]

Choose pivots:

p = 3,\quad q = 7

Partition:

region	values
< 3	[1, 2]
between	[3, 5, 7]
> 7	[9, 8]

Recursively sort each region:

Final result:

[1, 2, 3, 5, 7, 8, 9]

Correctness

The partition step ensures:

all elements before $p$ are smaller than $p$
all elements between $p$ and $q$ lie within the interval
all elements after $q$ are larger than $q$

Placing the pivots into their correct positions divides the array into three independent subproblems. Recursively sorting these regions produces a fully sorted array.

Complexity

case	time
best	$O(n \log n)$
average	$O(n \log n)$
worst	$O(n^2)$

In practice, dual pivot quicksort reduces constant factors compared to standard quicksort.

Space:

case	space
average	$O(\log n)$
worst	$O(n)$

Properties

property	value
stable	no
in-place	yes
partitioning	three-way
practical speed	very fast

Notes

Dual pivot quicksort often outperforms single pivot quicksort due to fewer comparisons and better cache usage. However, it is more complex and sensitive to implementation details.

It works best when pivot selection produces balanced partitions.

Implementation

def dual_pivot_quicksort(a):
    def sort(lo, hi):
        if lo >= hi:
            return

        if a[lo] > a[hi]:
            a[lo], a[hi] = a[hi], a[lo]

        p, q = a[lo], a[hi]

        lt = lo + 1
        gt = hi - 1
        i = lo + 1

        while i <= gt:
            if a[i] < p:
                a[i], a[lt] = a[lt], a[i]
                lt += 1
            elif a[i] > q:
                while a[gt] > q and i < gt:
                    gt -= 1
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
                if a[i] < p:
                    a[i], a[lt] = a[lt], a[i]
                    lt += 1
            i += 1

        lt -= 1
        gt += 1

        a[lo], a[lt] = a[lt], a[lo]
        a[hi], a[gt] = a[gt], a[hi]

        sort(lo, lt - 1)
        sort(lt + 1, gt - 1)
        sort(gt + 1, hi)

    sort(0, len(a) - 1)
    return a

func DualPivotQuickSort(a []int) {
	var sort func(int, int)

	sort = func(lo, hi int) {
		if lo >= hi {
			return
		}

		if a[lo] > a[hi] {
			a[lo], a[hi] = a[hi], a[lo]
		}

		p, q := a[lo], a[hi]

		lt, gt := lo+1, hi-1
		i := lo + 1

		for i <= gt {
			if a[i] < p {
				a[i], a[lt] = a[lt], a[i]
				lt++
			} else if a[i] > q {
				for a[gt] > q && i < gt {
					gt--
				}
				a[i], a[gt] = a[gt], a[i]
				gt--
				if a[i] < p {
					a[i], a[lt] = a[lt], a[i]
					lt++
				}
			}
			i++
		}

		lt--
		gt++

		a[lo], a[lt] = a[lt], a[lo]
		a[hi], a[gt] = a[gt], a[hi]

		sort(lo, lt-1)
		sort(lt+1, gt-1)
		sort(gt+1, hi)
	}

	sort(0, len(a)-1)
}