Overview

  • Divide and conquer
  • Select a pivot point, move items smaller than pivot point value to the left of pivot point and items large than pivot to the right.
  • Pick a new pivot point and repeat until sorted.
  • Closely related to Quick Select – which allows us to find the kth smallest/largest item.

Picking a Pivot

  • Median-of-three
    • Take the first, middle and last element and pick the median as a pivot.

Advantages

In place, not considering call stack

Disadvantages

In the worst case, if you make bad pivots takes n^2 run time