3-Way Quick Sort
Partition into smaller, equal and larger zones; the equal zone is final, so duplicates cost O(n).
Decision · step 3 of 19More Sorts: Three-way quicksort on duplicates
i = 1 holds 3. 3 < 7: swap it with index 0, the first pivot copy, so the smaller zone grows. Both lt and i move on.
What you will see
A middle "equal" region grows; duplicates settle in one pass.
Cost
| Best | O(n) |
|---|---|
| Average | O(n log n) |
| Worst | O(n^2) |
| Space | O(log n) |
Best case O(n) when all keys are equal.
Properties
- ✓ comparison based
- × stable
- ✓ in place
- ✓ adaptive
- × online
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, compare two runs.
Screen readers: Cells announce index, value and state (comparing, swapped, sorted); each step announces the comparison outcome and any move.
Reduced motion: Swaps become value crossfades with outline flashes; sorted-region growth is a static span change.
Before this
Related
A variant of
Taught by the same lesson
More Sorts covers these too, in the same run.