Randomised Quicksort and Expected Running Time

Quicksort is usually fast, but sometimes it is slow. Why?

Picture the worst luck. Every time the algorithm picks a pivot, it picks the very smallest or the very largest item in the part it is working on. Then one side of the partition gets everything except the pivot, and the other side gets nothing at all. The problem shrinks by only one item each round, so the total work is about 1 + 2 + 3 + ... + n, which grows like n squared. That is the bad case.

Now think about picking the pivot at random. The input cannot trick you anymore, because you do not follow a fixed rule. The only way to be unlucky is to keep drawing bad pivots by chance, and that is very unlikely. If you run the algorithm again and again on the same list, the time averages out to about n times log n.

So randomising the pivot does not remove the slow case. It can still happen. What changes is who controls it. Before, a sneaky input could force the slow case on purpose. After, the slow case is just bad luck, and the expected running time is n log n no matter what list you hand in.

The heart of quicksort is one step called partitioning. You take a part of the array, pick one item as the pivot, and rearrange the items so everything smaller than the pivot sits on its left and everything bigger sits on its right.

You walk through the array from left to right with one finger, call it j. You keep a second finger, call it q, that marks the end of the region already known to hold items smaller than the pivot.

Each time j lands on an item smaller than the pivot, you move q one step forward and swap that item into the small region. Each time j lands on an item bigger than the pivot, you do nothing except move j along.

The rule that stays true the whole way through is this: everything left of q is smaller than the pivot, and everything between q and j is bigger than the pivot. That rule is called the loop invariant. It is what lets you trust the result when the walk finishes.

One pass touches each item once, so partitioning a part of size n takes time proportional to n. That is why it is called linear time partitioning.

Some sorting algorithms, like selection sort and insertion sort, can take n squared steps in the worst case. When the list gets big, that gets slow fast. There is a smarter strategy called divide and conquer, and quicksort and merge sort both use it.

The idea has three parts. First, divide the problem into smaller pieces. Then, conquer by solving each piece, usually by calling the same method on the smaller pieces. Finally, combine the answers into one answer for the whole problem.

Quicksort divides by partitioning around a pivot. The pieces are the items below the pivot and the items above it. Then it sorts each side on its own, and the combine step is basically free because partitioning already put things in place.

Merge sort divides by cutting the list in half, sorts each half, and then merges the two sorted halves back together.

When the division is balanced, each round splits the work in half and there are about log n rounds. Each round does a total of about n steps, so the whole sort takes about n log n steps. That is much better than n squared for large lists.

The catch with quicksort is that division is only balanced if the pivots are good. That is exactly why people randomise the pivot.

When we talk about how fast an algorithm runs, we do not count exact seconds. Computers differ, and exact counts are fussy. Instead we describe how the running time grows as the input grows, and we use big-O notation to do it.

Big-O is a promise about the worst case. If we say an algorithm runs in O(n) time, we mean the number of steps grows no faster than some constant times n. The input could be friendly and finish sooner, but it will never be worse than that, except by the constant.

There is also big-Theta, which is stronger. Theta means the running time is pinned down from both sides: it grows at least as fast as one constant times the function and no faster than another constant times it. If binary search takes Theta(log n) in the worst case, then log n is the true growth rate, not just an upper limit.

For randomised quicksort this distinction matters. The worst case is still O(n squared), because bad luck can happen. But the expected running time is Theta(n log n), so on average it is pinned at n log n. The O gives a ceiling; the Theta tells you what you actually get on a typical run.