Insertion Sort vs Selection Sort
Insertion Sort and Selection Sort are both sorting. Play them side by side below, then see exactly where they diverge.
Either player can stop before each decision and ask what happens next: turn on Predict mode in its top bar.
Insertion Sort
Full topicTake the next value and slide it left past larger values into the sorted prefix.
The sorted prefix grows from the left. The new value shifts left one slot at a time until it fits.
Selection Sort
Full topicScan for the smallest value left, then swap it home. At most n-1 swaps.
A scan finds the minimum (marked candidate), then one swap plants it at the boundary.
How they differ
Both grow a sorted prefix one value at a time, in place, and both are O(n^2) on average. Insertion sort takes the next value as it comes and slides it left past larger ones, so a nearly sorted array costs close to O(n) and equal values keep their order. Selection sort scans the whole unsorted rest for its smallest value every time - O(n^2) whatever the input - but swaps at most n-1 times.
The run shown here takes 27 steps for Insertion Sort and 35 steps for Selection Sort. That count moves with the input - use the example tabs above either player to see it change.
| Cost | Insertion Sort | Selection Sort |
|---|---|---|
| best | O(n) | O(n^2) |
| average | O(n^2) | O(n^2) |
| worst | O(n^2) | O(n^2) |
| space | O(1) | O(1) |
| Property | Insertion Sort | Selection Sort |
|---|---|---|
| comparison based | ✓ | ✓ |
| stable | ✓ | × |
| in place | ✓ | ✓ |
| adaptive | ✓ | × |
| online | ✓ | × |