Two beginner sorts
Bubble sort and insertion sort both order data with simple nested passes, but they behave differently enough that one survives in practice while the other rarely does.
Bubble sort
- Repeatedly walk the list comparing adjacent pairs and swapping any that are out of order.
- After each full pass the largest remaining value has bubbled to its place at the end.
- It does many swaps and is mostly valued as a teaching example.
Insertion sort
- Grow a sorted region at the front by taking the next element and sliding it left into place among the already sorted items.
- It moves elements rather than swapping pairs, and it stops shifting as soon as the spot is found.
Why insertion sort earns its keep
- On data that is already nearly sorted, it does almost no work, finishing in close to a single pass.
- It is stable and sorts in place with tiny overhead.
- Libraries switch to it for small subarrays inside bigger sorts because its constant factors are low.
Key idea
Bubble sort mostly teaches the idea of swapping neighbours, while insertion sort earns real use by flying through nearly sorted data with low overhead.