3-Way Quick Sort
Partition into smaller, equal and larger zones. The equal zone is final, so duplicates cost O(n).
More 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.
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
- Yes: Comparison based
- No: Stable
- Yes: In place
- Yes: Adaptive
- No: Online
Before this
A variant of
Taught by the same lesson
More Sorts covers these too, in the same run.