How Quicksort Turns One List Into Smaller Ones
Quicksort organizes a list by choosing one item as a pivot. It compares the other items with that pivot, then groups those that belong before it on one side and those that belong after it on the other. The pivot is now in its final position; the same process can be applied separately to the two smaller groups.
For example, sorting a list of numbers around 5 might leave the smaller numbers on one side and the larger numbers on the other. Quicksort does not need to know the final order of either group yet. It keeps partitioning until each group is so small—often just one item—that it is already sorted.
Why Balanced Splits Save Work
If each pivot falls near the middle of its group, every round shrinks the groups substantially. A list of 1,024 items, for instance, can be split into groups of about 512, then 256, and so on. That takes roughly ten rounds of splitting, because ten halvings reduce 1,024 to 1.
Across each round, the algorithm examines about as many items as the list contains. With roughly logarithmically many rounds, the total work grows around n log n—where n is the number of items—instead of comparing every pair, which would take about n² comparisons.
The Pivot Is the Tradeoff
A pivot that repeatedly lands near an end produces lopsided partitions: one group is nearly the whole list, while the other is tiny. Then each round removes little, and the work can grow toward n². Quicksort’s speed therefore depends on how well its pivots divide the data; implementations use pivot-selection strategies to make consistently poor splits less likely.
That tradeoff is the memorable part: quicksort can sort a large list quickly not by checking every possible ordering, but by repeatedly placing one item and narrowing the problem around it.
