# Dual Pivot Quicksort

# 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

```text id="v8q3ps"
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

```python id="v2p7qk"
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
```

```go id="x6k2tr"
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)
}
```