Overview
3-Way Quicksort is ordinary quicksort with a smarter partition. Instead of splitting the array into 'less than pivot' and 'not less than pivot', it splits into three regions in a single scan: values below the pivot, values equal to it, and values above it.
That middle region is the whole point. Once a batch of equal keys lands there it is already in final position and never gets looked at again, so an array of a few distinct values sorts in near-linear time — exactly the input where plain quicksort degrades to O(n²). The partition scheme is Dijkstra's Dutch national flag problem, named for the three colour bands it produces.
How 3-Way Quicksort works
- Pick a pivot, then keep three moving indices: lt marks the end of the 'less than' region, gt marks the start of the 'greater than' region, and i is the element being examined.
- If the current element is less than the pivot, swap it into the lt boundary and advance both lt and i.
- If it is greater than the pivot, swap it down to the gt boundary and move gt left — but do not advance i, because the value just swapped in has not been examined yet.
- If it equals the pivot, leave it where it is and just advance i; it is already inside the middle band.
- Stop when i passes gt, then recurse on the two outer regions only. Everything equal to the pivot is finished.
When to use it
- Any dataset with heavy duplication: status flags, categories, ratings, boolean-ish columns, or timestamps rounded to the day.
- Sorting by a low-cardinality key before grouping — the equal band gives you the groups for free.
- As the default in-place sort in libraries that cannot assume anything about the input distribution.
- Not worth the extra branches when keys are nearly all distinct — plain quicksort does less work per element there.
Complexity analysis
Average time stays O(n log n), the same as standard quicksort. The gain shows at the extremes: with only a handful of distinct keys, each partition finishes a large block permanently and the total collapses toward O(n). The O(n²) worst case survives in theory — an adversarial pivot sequence on distinct keys — which is why real implementations randomise or median-of-three the pivot. Space is O(log n) for the recursion stack, since the partition itself is in place.
Frequently asked questions
Why does plain quicksort struggle with duplicates?
A two-way partition has to put every key equal to the pivot on one side or the other. An array where all keys are identical therefore splits into one empty part and one part of size n − 1, which is the O(n²) shape. The three-way scheme removes those keys from the problem entirely.
Is it stable?
No. The partition swaps elements across long distances, so two records with the same key can come out in a different relative order than they went in. If you need stability, merge sort is the usual answer.
How is this different from counting sort on low-cardinality data?
Counting sort needs to know the key range in advance and allocates a bucket per possible key, which only works for small integer-like keys. 3-way quicksort makes no assumption about the keys beyond being comparable, and sorts in place.