Keeping the Stack Shallow by Recursing Into the Smaller Side

Quicksort's stack of open calls can grow n deep on a bad input, but it never needs to: recursing only into the smaller side of each partition, and handling the larger side with a loop, keeps the stack at most about log₂ n calls deep on every input. This card shows why that works, the depths from a run, and what the change does not fix.

Each call partitions its range and leaves two sides to sort. The plain version calls itself on both. The second of those calls is the last thing the function does, so instead of calling, it can set low or high to that side's bounds and go round a while loop: the same work, with no new call on the stack. That leaves a choice of which side to loop over. Loop over the larger side and recurse into the smaller, and each call on the stack covers at most half the range of the call below it. A range can be halved only about log₂ n times before it holds one item, so no input can push the stack deeper than that.

A run sorted the numbers 0 to 999, already in order, four ways, and recorded the deepest chain of calls that partitioned something. The random pivots came from a generator seeded with 42.

The third row shows what the change does and what it does not. The stack stayed at one call, because with a last-item pivot on sorted input the smaller side was always empty and the loop did all the work. The time did not improve at all: the run counted 499,500 comparisons for that row, exactly as many as the first. Recursing into the smaller side bounds memory on every input, and only a good pivot bounds time. The two fixes are independent, which is why a quicksort written for real use has both.

Recursing into the left side every time and looping over the right is not the same change, even though it also replaces one call with a loop. On sorted input with a last-item pivot the left side is the large one, and the same run measured that variant at 999 calls deep, no better than recursing into both sides. The bound comes from choosing the side by its size, not from the loop.

The change matters wherever the stack is limited: Python's default of 1,000 nested calls, a thread created with a small fixed stack, or code on a small device. It costs one subtraction and one comparison per partition.