Comparing sorting methods

Two people sort the same stack of cards: one keeps swapping neighbours, the other always looks for the smallest card and puts it at the front. Both of them finish, but who does less work? This is exactly how computer scientists compare sorting methods: they count the comparisons and the swaps. Let us do the same.

Bubble sort: hard-working but slow

You already know bubble sort: it keeps comparing two neighbours and swaps them if they are the wrong way round. The biggest number rises to the end like a bubble, then everything starts over. The problem: there is an enormous amount of comparing and swapping. For 5 numbers it is up to 10 comparisons in the worst case, for 10 numbers already 45. Double the count and the work roughly quadruples.

Selection sort: minimum to the front

Selection sort takes a different approach: search the whole list for the smallest number and move it to the front. Then find the smallest in the unsorted rest and put it in second place, and so on. To find the minimum of 5 numbers you keep the first number in mind and compare it with each of the others: 4 comparisons, always one fewer than there are numbers. In the rest it is 3, then 2, then 1, so also 10 comparisons in total. On comparisons the two methods are close, but selection sort swaps far less often: at most once per round.

Why clever methods win

For 10 numbers the difference does not matter. But for a million entries, bubble sort and selection sort need around 500 billion comparisons. Clever methods like merge sort keep splitting the list into halves and get by with about 20 million comparisons: roughly 25000 times fewer. That is why sorting feels instant on your phone even though huge amounts of data are involved. The choice of method decides, not the speed of the device.