Sorting

Your playlist by title, your photos by date, the game leaderboard by points: sorted things are everywhere. That's no accident, because in sorted data you find everything much faster. But how do you bring a jumbled list into order?

Why sort?

From the searching topic you know: binary search finds entries in a flash, but only in sorted lists. Sorting is the groundwork that makes fast searching possible in the first place. Sort once, then search quickly as often as you like: that trade is almost always worth it.

Comparing and swapping

One simple sorting idea goes like this: you always compare two neighbours in the list. If they are in the wrong order, you swap them. Then you move one position along and compare the next pair. Once you have walked through the whole list, the largest element has drifted to the back, just like a bubble rising in water. That's why this method is called bubble sort. You can count the comparisons of such a pass directly: with 6 entries there are 5 pairs of neighbours, so 5 comparisons, always one fewer than the list has entries.

Multiple passes

One pass is usually not enough, because it only pushes the largest element safely to the end. So you start again from the front, comparing and swapping once more. With every pass, the next largest element lands in its place. With 6 entries at most 5 passes are therefore needed: once 5 elements sit safely at the back, only the free spot at the very front is left for the last one. And when a complete pass needs no swap at all, you know for sure that the list is fully sorted.

Sorting at scale

Computers sort millions of entries every day: search results, contact lists, prices in online shops. For huge amounts of data there are more refined methods than bubble sort, but the core idea stays the same: order emerges from many small comparisons. Once you understand the principle, the fast methods become easier to understand too.