Two questions every sharp learner asks: "does it keep ties in order?" and "what should I use instead?"
A sort is stable when equal keys keep their original relative order. Bubble sort is stable because it only swaps when a[j] > a[j + 1], strictly. Two equal neighbours never swap, so they can never pass each other.[1]
type Row = { name: string; age: number };
const rows: Row[] = [
{ name: 'Ana', age: 30 }, { name: 'Bo', age: 25 }, { name: 'Cy', age: 30 },
];
// sort by age with a[j].age > a[j+1].age -> Bo, Ana, Cy (Ana still before Cy)
// change > to >= -> Bo, Cy, Ana (stability lost)> to >= live and rerun. One character breaks stability. Learners remember the demo, not the definition.Insertion sort also runs O(n²) worst case and O(n) on sorted input, and is also stable. Yet it is roughly 5x faster than bubble sort in practice.[1] Why: bubble sort does a full swap (three writes) for every inversion; insertion sort shifts elements with one write each and places the key once.[2]
function insertionSort(a: number[]): number[] {
for (let i = 1; i < a.length; i++) {
const key = a[i];
let j = i - 1;
while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
a[j + 1] = key;
}
return a;
}| Bubble | Insertion | |
|---|---|---|
| Worst / best | O(n²) / O(n) with flag | O(n²) / O(n) |
| Stable | Yes | Yes |
| Writes per inversion | 3 (swap) | 1 (shift) |
| What each pass fixes | Largest of the prefix, to the end | Grows a sorted prefix by one |
| Real use | Teaching only | Small n, base case of hybrid sorts |
Sedgewick and Wayne, Elementary Sorts: slides on insertion sort invariants and why it wins among simple sorts.
Anything unclear? Ask your teaching agent - it wrote this lesson and can go deeper on any point.