Sorting looks like the most boring job a computer does. Yet it is where one idea, how the work grows as the pile grows, shows up most plainly. Two methods can both be perfectly correct and still differ by a factor of twenty-five thousand on a big enough list.

Two ways to put things in order

Bubble sort walks along the row, compares each neighbouring pair, and swaps them if they are the wrong way round. Repeat until a whole pass makes no swaps. It is easy to write and easy to follow, and it is slow.

Merge sort splits the row in half, sorts each half the same way, then merges the two sorted halves by repeatedly taking the smaller of the two front items. The idea is credited to John von Neumann, in 1945. Sorted halves are cheap to combine, so the real work is just a few levels of halving.

Race them

Both lanes get the same shuffled bars. Press Race and watch the counters: every comparison is one step of work. Then drag the size up and race again.

Why the gap keeps widening

Bubble sort compares neighbours, and each pass can only move an item one place toward its home. In the worst case it needs about n(n − 1)/2 comparisons. Double the list and the work roughly quadruples.

Merge sort halves the list about log₂ n times, and each level of halving costs at most about n comparisons to merge. That gives roughly n × log₂ n. Double the list and the work only a little more than doubles.

Scale it up

Drag the slider to pick a list size. The calculator uses the formulas above, and assumes a computer that can do one billion comparisons a second.

At a million items, bubble sort needs about 5×10¹¹ comparisons, around eight minutes at that speed. Merge sort needs about 2×10⁷, around a fiftieth of a second. At a billion items, bubble sort would take about 16 years, while merge sort takes about half a minute.

Is n log n the best you can do?

For methods that only learn by comparing two items, yes. There are n! possible orderings, each comparison gives at most a yes or a no, so you need at least log₂(n!) comparisons, which grows like n log₂ n. Merge sort comes close to that floor. Many real libraries use merge-based hybrids; Python's built-in sort, Timsort, is one.

The takeaway is not “never use bubble sort”. For a dozen items nobody can tell. The takeaway is to ask, of any method, what happens to the work when the input gets ten times bigger?