## Algorithm

*# choose pivot*
swap a[n,rand(1,n)]
*# 3-way partition*
i = 1, k = 1, p = n
while i < p,
if a[i] < a[n], swap a[i++,k++]
else if a[i] == a[n], swap a[i,--p]
else i++
end
*→ invariant: a[p..n] all equal*
*→ invariant: a[1..k-1] < a[p..n] < a[k..p-1]*
*# move pivots to center*
m = min(p-k,n-p+1)
swap a[k..k+m-1,n-m+1..n]
*# recursive sorts*
sort a[1..k-1]
sort a[n-p+k+1,n]

## Properties

- Not stable
- O(lg(n)) extra space
- O(n
^{2}) time, but typically O(n·lg(n)) time
- Adaptive: O(n) time when O(1) unique keys

## Discussion

The 3-way partition variation of quick sort has slightly higher
overhead compared to the standard 2-way partition version. Both
have the same best, typical, and worst case time bounds, but
this version is highly adaptive in the very common
case of sorting with few unique keys.

The 3-way partitioning code shown above is written for clarity rather than optimal
performance; it exhibits poor locality, and performs more swaps than necessary.
A more efficient but more elaborate 3-way partitioning method is given in
Quicksort is Optimal
by Robert Sedgewick and Jon Bentley.

When stability is not required, quick sort is
the general purpose sorting algorithm of choice.
Recently, a
novel dual-pivot variant
of 3-way
partitioning has been discovered that
beats the single-pivot 3-way partitioning method
both in theory and in practice.

## Key

- Black values are sorted.
- Gray values are unsorted.
- Dark gray values denote the current interval.
- A pair of red triangles mark k and p (see the code).