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?

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: