Same result, different work: comparing sorting algorithms

If you sort the same list with bubble sort or with merge sort, you get the same answer. The difference is the work done on the way, and that difference grows quickly as the list gets longer.

Why the work differs

• Bubble sort repeatedly compares neighbours and swaps them. It is simple, but the work grows with the square of the list size (O(n²)).
• Merge sort splits the list, sorts the halves and merges them. The work grows like n log n, and equal items keep their original order (it is stable).
• Quick sort picks a pivot and splits the list around it. It is usually very fast, about n log n, but a bad choice of pivot can make it O(n²).
• Counting sort does not compare items at all. It counts how many times each value appears, so it is very fast when the values are in a small range.

A feeling for the numbers

For 1,000 items, n² is about 1,000,000 steps, while n log n is only about 10,000. That is roughly a hundred times less work, and the gap keeps widening as the list grows.

What the step view shows

Reading the complexity table is one thing. Watching an algorithm compare and swap, one step at a time, shows where the work goes. The Sorting experiment records every comparison and swap with a short explanation, and you can compare two algorithms on the same list.

Open the Sorting experiment