• Consider a recursive call to partition() on an index range of size s
  • Good call:
    both low..pivot-1 and pivot+1..high shorter than ¾·s
  • Bad call:
    one of low..pivot-1 or pivot+1..high greater than ¾·s
• Probability that a call is good: 0.5
  (because half the possible pivot elements cause a good call)

6  3  7  5  8  2  4  1

4  3  6  5  1  2   | 7 |   8

Example of a good call:

4  3  6  5  1  2   | 7 |   8

1  2   | 3 |   5  6  4   | 7 |   8