Say you want to put a row of books in order of height. You can't take in the whole row at a glance the way you might wish. The honest way is to look at just two books next to each other, and if the left one is taller, swap them. That one move, compare two and maybe swap, is all a computer can really do. The naive way, called bubble sort, just keeps walking the whole row swapping neighbours until nothing needs swapping. It works, but it does a huge number of compares. A cleverer plan, quicksort, splits the books into a smaller pile and a bigger pile and sorts each the same way, finishing far quicker. Press play in the simulator, switch between the two, and watch the comparison counter.
Most people think a computer can survey a whole list and drop each item into place. In fact its only move is to compare two items and maybe swap them; every sorting method is just a recipe for scheduling those comparisons.
What's actually happening
It is tempting to imagine a computer sorting the way you might tidy a shelf, taking in the whole thing and dropping each item where it belongs. It cannot. At the lowest level it has exactly one tool: pick two items, compare them, and swap them if they are in the wrong order. Every sorting method ever invented, from the simplest to the ones running inside your phone right now, is just a different recipe for which pairs to compare and when. The whole art is in the scheduling.
The naive recipe is bubble sort, and it is exactly what its name suggests. Walk along the list comparing each neighbour to the next, swapping any that are out of order, and the biggest value slowly bubbles up to the end. Then do it again for the rest, and again, until a clean pass makes no swaps. It always works, and it is easy to understand, but it is wasteful: for a list of n items it does on the order of n² comparisons. Sixteen items cost about 120 comparisons; a thousand items cost roughly half a million. The work grows with the square of the size, and that gets brutal fast.
Quicksort wins by refusing to grind through the whole list over and over. It picks one item as a pivot, then splits everything else into a smaller-than-pivot pile and a bigger-than-pivot pile in a single pass, and then sorts each pile the same way. Because every split roughly halves the problem, the total work comes out around n log n: about 64 comparisons for sixteen items, around 10,000 for a thousand. That sounds like a modest saving until the lists get large. At a million items, n² versus n log n is the difference between billions of comparisons and tens of millions, between an operation that takes days and one that takes a fraction of a second. Same primitive move; wildly different bill.
Same compare-and-swap move, but quicksort's halving turns n² into n log n, which is days versus seconds at scale.
- 1Deal yourself about ten playing cards in a row, face up, in random order.
- 2Go left to right comparing each card with its right-hand neighbour, swapping any pair that is out of order. Reach the end, then start over from the left.
- 3Keep repeating until a full left-to-right pass needs no swaps. Count your swaps, then imagine doing this for a thousand cards, and you will feel exactly why quicksort exists.
Common questions
It picks a pivot and splits everything else into a smaller-than-pivot pile and a bigger-than-pivot pile, then sorts each the same way. Because every split roughly halves the problem, the total work comes out around n log n instead of n².
It widens explosively with size. At a thousand items bubble sort does about half a million comparisons to quicksort's ten thousand; at a million items it is the difference between days of work and a fraction of a second.
No. Real libraries use n log n methods like quicksort, mergesort or hybrids such as Timsort. Bubble sort survives only as a teaching example, because it shows how badly n² scales.