Bubble vs Selection vs Insertion Sort

Bubble, selection and insertion sort all take O(n²) time in the worst case, so Big O alone cannot choose between them, and their counts on real inputs can. This card runs the three on the same three inputs, compares their stability, and names the one place insertion sort still beats an O(n log n) sort.

The inputs are seven items each: 1 to 7 already sorted, 2 1 3 4 6 5 7 with two neighbouring pairs exchanged, and 7 to 1 reversed. For insertion sort the moves are shifts, and for the other two they are swaps.

Read the table by row. Selection sort's comparisons never move from 21, because its scan cannot stop early, and its swaps never pass n − 1. Bubble sort and insertion sort make one move per inversion, so their moves are equal on every input, and both fall to n − 1 comparisons on sorted input. They part on the nearly sorted input: bubble sort needs a whole second pass to see that nothing moves, 11 comparisons, while insertion sort stops each key as soon as it finds its place, 7.

Stability follows from how far an item moves. Bubble sort and insertion sort move an item only past a neighbour strictly larger or smaller than it, so equal items keep their order. Selection sort's swap carries an item from the front of the unsorted part to wherever the minimum was, past anything in between, equal items included.

Insertion sort is the one that survives in practice, inside the library sorts. CPython's list.sort sorts a list shorter than 64 items with binary insertion sort alone, and uses the same step to lengthen short runs in longer lists (Objects/listobject.c, Python 3.14). Java's Arrays.sort on an int[] switches to insertion sort once a part of the array is small, below 44 or 65 items depending on where the part sits (DualPivotQuicksort.java, JDK 25). V8, the engine under Chrome and Node, extends short runs with insertion sort inside its Timsort. On a few dozen items, insertion sort's tiny loop and its speed on nearly sorted data beat the bookkeeping an O(n log n) sort spends on recursion and merging.

So choose by the input, not the Big O: insertion sort for small or nearly sorted data, selection sort only when moving an item is what costs, and bubble sort for teaching.