# Three Way Quicksort

# Three Way Quicksort

Three way quicksort extends quicksort by handling duplicate keys efficiently. Instead of partitioning into two parts, it splits the array into three regions:

* elements less than the pivot
* elements equal to the pivot
* elements greater than the pivot

This reduces unnecessary comparisons when many elements are equal.

## Problem

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

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

## Idea

Use a three way partition (also called Dutch National Flag partition). Maintain three regions:

$$
[ < p ;|; = p ;|; > p ]
$$

During partitioning, elements are rearranged into these regions in one pass.

## Algorithm

```text id="p7s2xn"
three_way_quicksort(A, lo, hi):
    if lo >= hi:
        return

    lt = lo
    i = lo
    gt = hi
    pivot = A[lo]

    while i <= gt:
        if A[i] < pivot:
            swap A[lt], A[i]
            lt += 1
            i += 1
        else if A[i] > pivot:
            swap A[i], A[gt]
            gt -= 1
        else:
            i += 1

    three_way_quicksort(A, lo, lt - 1)
    three_way_quicksort(A, gt + 1, hi)
```

## Example

Let:

$$
A = [3, 5, 3, 2, 3, 1, 5]
$$

Choose pivot $3$.

Partition result:

| region | values    |
| ------ | --------- |
| < 3    | [2, 1]    |
| = 3    | [3, 3, 3] |
| > 3    | [5, 5]    |

Recursively sort left and right:

Final result:

$$
[1, 2, 3, 3, 3, 5, 5]
$$

## Correctness

The partition step ensures:

* all elements in the left region are less than the pivot
* all elements in the middle region equal the pivot
* all elements in the right region are greater than the pivot

The pivot region is already in final position. Recursively sorting the left and right regions produces a fully sorted array.

## Complexity

| case    | time               |
| ------- | ------------------ |
| best    | $O(n)$ (all equal) |
| average | $O(n \log n)$      |
| worst   | $O(n^2)$           |

Three way partition improves performance when duplicates are frequent, often reducing recursion depth.

Space:

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

## Properties

| property              | value       |
| --------------------- | ----------- |
| stable                | no          |
| in-place              | yes         |
| duplicate handling    | excellent   |
| practical performance | very strong |

## Notes

Three way quicksort is especially effective when the input contains many repeated values. Standard quicksort degrades in such cases because it repeatedly partitions equal elements.

This variant avoids that by grouping equal elements in a single step.

## Implementation

```python id="m2x7rt"
def three_way_quicksort(a):
    def sort(lo, hi):
        if lo >= hi:
            return

        lt = lo
        i = lo
        gt = hi
        pivot = a[lo]

        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
            else:
                i += 1

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

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

```go id="q9s4le"
func ThreeWayQuickSort(a []int) {
	var sort func(int, int)

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

		lt, i, gt := lo, lo, hi
		pivot := a[lo]

		for 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, len(a)-1)
}
```