Sorting Algorithms, Visualised

“Put this list in order” sounds trivial — until you have to spell out exactly how. That is what a sorting algorithm does, and the different ways of doing it reveal, in miniature, the whole art of thinking about efficiency.

What sorting algorithms do

A sorting algorithm takes a list of items — numbers, names, records — and rearranges them into order. There are many ways to reach the same sorted result, so we need a fair way to compare them. Almost every one boils down to two basic operations: comparisons (is this item bigger than that one?) and swaps or writes (move an item to a new position).

Counting comparisons and swaps — rather than timing the code on one particular computer — lets us judge an algorithm independently of the machine it runs on. It is the honest measure of how hard the algorithm is working.

The best algorithm is not the one that finishes first on your laptop — it is the one that does the least work as the list grows.

See it: watch them sort

Reading pseudocode for a sort is one thing; seeing it move is another. In the visualiser below, each bar is a number and its height is its value. Pick an algorithm, press play, and watch the comparison and swap counters climb as the bars settle into order.

Try the same list with each algorithm and compare the final counts — the differences are the whole story.

Bubble vs insertion vs merge

The four classic algorithms reach the same destination by very different routes.

Bubble sortwalks along the list comparing each adjacent pair and swapping any that are out of order. After one full pass the largest value has “bubbled” to the end; it repeats, one fewer element each time, until a pass makes no swaps at all.

Insertion sortgrows a sorted section at the front of the list. It takes the next unsorted item and slides it back into its correct place among the already-sorted ones — much like arranging a hand of playing cards.

Selection sortrepeatedly scans the unsorted part to find the smallest remaining item and places it at the front of that part. It does very few swaps — one per pass — but many comparisons.

Merge sorttakes a divide-and-conquer approach: split the list in half, split each half again, and keep going until every piece is a single item (which is trivially “sorted”). Then it repeatedly merges pairs of sorted pieces back together in order, until the whole list is rebuilt.

Counting the work

Run each algorithm on a longer and longer list and the counters tell a stark story. Bubble, insertion and selection sortall do roughly n × n work on a list of n items — they are O(n²). Double the list and they do about four times the work. Merge sort is far gentler at O(n log n): doubling the list barely more than doubles the work.

Common mistakes

Practice

Where next?

The O(n²) and O(n log n) labels above are Big-O notation — the standard language for how an algorithm’s cost grows with the size of its input. It is the natural next step once these sorts make sense.