## Quick Sort

How can we SPLIT L into L1 and L2 so that we can *safely* use
JOIN instead of MERGE?
Answer: when everything in L1 is smaller than everything in L2.

**Algorithm:** pick a CUTOFF, put in L1 the elements of L
smaller than CUTOFF, and in L2 the ones bigger than CUTOFF.

How to choose CUTOFF?

- must be cheap to compute
- must be in the range of L
- should divide L in 2 piece of roughly equal size

Best choice: CUTOFF = median(L) = element of L greater than exactly
half the values in L.

Quick Sort actually splits the list into 3 pieces:

- L1 = {elements with KEY < CUTOFF}
- LC = {elements with KEY = to CUTOFF}
- L2 = {elements with KEY > CUTOFF}