How does insertion-sort differ from selection-sort, given that both are $O(n^2)$?
They pay in opposite phases: insertion-sort does the sorting work on the way in (each element is placed at its correct position), selection-sort on the way out (each removal searches for the minimum).
* The same total, paid in opposite phases — cheap insertion buys expensive extraction, and vice versa. *
| Insertion-sort | Selection-sort | |
|---|---|---|
| Internal sequence | kept sorted at all times | kept unsorted |
| Insert phase | find the right position, $O(n)$ per element → $O(n^2)$ | append anywhere, $O(1)$ each → $O(n)$ |
| Remove phase | take from the front, $O(1)$ each → $O(n)$ | scan the remainder for the minimum → $O(n^2)$ |
| Total | $O(n^2)$ | $O(n^2)$ |
Insertion-sort's expensive phase is the sum $1 + 2 + \dots + n = \frac{n(n+1)}{2}$, because the sorted sequence it must search through grows by one element each time. Selection-sort's expensive phase is the same sum counted downwards. Same total, mirrored.
Worked on $(7,4,8,2,5,3,9)$, insertion-sort's sequence is already sorted at every step: $(7)$, $(4,7)$, $(4,7,8)$, $(2,4,7,8)$, $(2,4,5,7,8)$, $(2,3,4,5,7,8)$, $(2,3,4,5,7,8,9)$ — then removal is just reading it off the front.
Why the pair is taught together: it is the first clear instance of a bargain that runs through the whole subject — a structure that makes insertion cheap makes extraction expensive, and vice versa. You do not escape the cost, you choose where to pay it.
Go deeper:
Insertion sort — the adaptive behaviour that makes it the standard choice for small or nearly-sorted arrays.