The idea: three ways to grow a sorted part
This page copies one array into three lanes and runs insertion sort, selection sort and bubble sort on them at the same time. One step is one comparison in every lane, so the lane that finishes first is the one that needed the fewest comparisons. Two scoreboards count the work: comparisons (looking at two values) and swaps (exchanging two values).
All three keep a sorted part that grows by one value at a time. They differ in where that part is and how a new value gets into it.
Insertion sort
Take the next value and slide it left, one swap at a time, while its left neighbour is larger. The first neighbour that is not larger stops it. The left part is always sorted, but not final: a later small value can still push into it (light green bars).
Because it stops early, insertion sort is adaptive: on input that is already nearly in order, each value takes one or two comparisons and the whole sort is about n comparisons (Demo: nearly sorted: 13 comparisons for 12 values).
Selection sort
Scan the unsorted rest for the smallest value (yellow bar), then swap it to the front of the rest, where it is final (green). The scan has to look at every remaining value, so selection sort always makes n(n−1)/2 comparisons, even when the array is already sorted (Demo: already sorted: 66 comparisons for 12 values, the other two need 11).
In return it makes at most one swap per pass, n − 1 in total. When writing a value is much more expensive than reading one (flash memory, large records), that is the number that matters (Demo: reversed: 6 swaps against 66).
Bubble sort
Walk the array left to right, swapping each pair of neighbours that is out of order. The largest value is carried to the end of the pass, where it is final. This page's version stops after a pass with no swap, so sorted input costs one pass.
Large values near the start ("rabbits") move right fast, but small values near the end ("turtles") move left only one place per pass. One small value at the end forces every pass (Demo: smallest value last: bubble 66 comparisons, insertion 21).
Counting the work
An inversion is a pair of values in the wrong order. Insertion and bubble only ever swap neighbours that are out of order, and each such swap fixes exactly one inversion. So both make exactly one swap per inversion, and their swap counts are always equal: 0 on sorted input, n(n−1)/2 on reversed input, about n²/4 on random input.
Comparisons differ. Insertion makes about one comparison per swap plus one per value, bubble keeps comparing until a clean pass, and selection compares every pair regardless.
This page's own numbers, averaged over 500 random arrays (comparisons / swaps):
| n | Insertion | Selection | Bubble |
|---|---|---|---|
| 8 | 19.2 / 13.8 | 28 / 5.3 | 25.9 / 13.8 |
| 12 | 42.4 / 33.4 | 66 / 8.8 | 62.3 / 33.4 |
| 16 | 72.8 / 60.1 | 120 / 12.5 | 113.4 / 60.1 |
When to pick which
| Insertion | Selection | Bubble | |
|---|---|---|---|
| Comparisons, sorted input | n − 1 | n(n−1)/2 | n − 1 |
| Comparisons, reversed input | n(n−1)/2 | n(n−1)/2 | n(n−1)/2 |
| Swaps | one per inversion | at most n − 1 | one per inversion |
| Stable (equal keys keep their order) | yes | no | yes |
| Pick it when | small or nearly sorted arrays; the base case inside TimSort and introsort | writes are expensive and reads are cheap | teaching; checking that an array is sorted in one pass |
See also Comparison Sorting, which steps through each of these sorts on its own with every comparison explained, Sorting Race for faster sorts, and Quick Sort vs Merge Sort.
What the page leaves out
Insertion sort is usually written with shifts (move larger values right one place, then write the new value once) instead of swaps; that does the same comparisons with about a third of the writes. Also left out: binary insertion sort, which finds the place with binary search; cocktail shaker sort, which bubbles in both directions to move turtles faster; Shell sort, which runs insertion sort on values far apart first; equal keys and stability, since every value here is distinct; and real timings, where cache behaviour and branch prediction matter as much as these counts.