All simulators
Sorting & searching
Race bubble, insertion and merge sort, then binary search a sorted shelf. Count every comparison.
Race bubble, insertion and merge sort, then binary search a sorted shelf. Count every comparison.
Bubble sort
step 0 / 46
Bubble sort walks along the list comparing neighbours. A bigger number on the left gets swapped to the right.
A computer can only compare two numbers at a time, so we measure a sorting algorithm by how many comparisons it makes. Bubble sort swaps neighbours that are in the wrong order, pass after pass. Insertion sort slides each new number left until it fits. Merge sort splits the list in half, sorts each half, then zips the halves together.
On a reversed list, bubble and insertion sort compare every pair: n(n−1)/2 comparisons. Merge sort never needs more than about n × log₂ n, where log₂ n is how many times you can halve n before you reach 1 (for 8 it is 3: 8 → 4 → 2 → 1). For 8 numbers that is 28 against at most 17. For 1,000 numbers it is about 500,000 against under 10,000.
Takeaway: the same job can take very different amounts of work. The best algorithm depends on the input: insertion sort is excellent on lists that are already nearly sorted.
The list
Same list, three algorithms
| Algorithm | Comparisons | Swaps / moves |
|---|---|---|
| Bubble | 27 | 13 |
| Insertion | 19 | 13 |
| Merge | 17 | 24 |
Bar length is out of 28 = n(n−1)/2, the most comparisons bubble or insertion sort can ever need for n = 8. Merge sort writes every number into place at each level, so its “moves” are not swaps.
A computer can only compare two numbers at a time, so we measure a sorting algorithm by how many comparisons it makes. Bubble sort swaps neighbours that are in the wrong order, pass after pass. Insertion sort slides each new number left until it fits. Merge sort splits the list in half, sorts each half, then zips the halves together.
On a reversed list, bubble and insertion sort compare every pair: n(n−1)/2 comparisons. Merge sort never needs more than about n × log₂ n, where log₂ n is how many times you can halve n before you reach 1 (for 8 it is 3: 8 → 4 → 2 → 1). For 8 numbers that is 28 against at most 17. For 1,000 numbers it is about 500,000 against under 10,000.
Takeaway: the same job can take very different amounts of work. The best algorithm depends on the input: insertion sort is excellent on lists that are already nearly sorted.
Things to try