Quick Sort

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}