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

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

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

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)
}