AlgoScope

3-Way Quick Sort

Partition into smaller, equal and larger zones. The equal zone is final, so duplicates cost O(n).

Sorting, algorithm, intermediate
Value 3 against pivot 7.range 0-830717212374157620738ltigt3 < 7
Value 3 against pivot 7.range 0-830717212374157620738ltigt3 < 7

More Sorts: Three-way quicksort on duplicates

Decision, step 3 of 19

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.

How more sorts works

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

A variant of

Taught by the same lesson

More Sorts covers these too, in the same run.