What is the invariant of the classic partition loop?

• Everything left of finger q is smaller than the pivot
• Finger j never moves
• The pivot stays at the first position

What does the partition step do?

• Sorts the whole array at once
• Rearranges items so smaller ones sit left of the pivot and bigger ones right
• Picks a random number and stops

A sorted input makes fixed-pivot quicksort shrink the problem by only one item per round.

In the worst case, rounds cost 5, 4, 3, 2, then 1 comparisons. Type the total.

Why is that shrinking pattern quadratic?

• Each round costs one step only
• The work adds up like 1 plus 2 up to n
• The pivot changes size

What does picking the pivot at random change?

• Bad cases become bad luck that no input can force
• The algorithm becomes always faster than merge sort
• Partitioning needs no comparisons

Partitioning scans its section once, doing work proportional to its length.

Which claim about randomised quicksort is wrong?

• Its expected time is n log n over the random picks
• No input can force the worst case
• Its quadratic worst case disappears entirely