Insertion sort and selection sort are the two "simple" sorts everyone meets early. Both are O(n²) and both sort in place, but they think about the problem in opposite ways. Insertion sort builds a sorted hand of cards by slotting each new card into place; selection sort repeatedly hunts for the smallest remaining value and drags it to the front. This lesson animates insertion sort and contrasts it with selection sort in the notes.
Insertion sort in one idea. Keep a sorted region on the left. For each new element, treat it as a "key", slide every bigger element in the sorted region one slot to the right, and drop the key into the gap that opens up.
Intuition
Picture sorting a hand of playing cards. You pick up cards one at a time. Each new card, you slide left past the cards that are bigger than it until you hit one that is smaller — then you tuck it in right there. The cards already in your hand stay sorted the whole time; you are only ever finding the home for one new card.
That is insertion sort exactly. The "hand" is the sorted prefix on the left of the array, and the "new card" is the key at index i.
Walk through it
Step through the animation on the right. It sorts [5, 2, 4, 1]. The sorted region (green) starts as just the first element. Each round, the pointer i picks the next element as the key (blue), and j scans back through the sorted prefix.
Watch the shift: whenever an element is bigger than the key, it slides one box to the right (you will see it move) to make room — that is the a[j + 1] = a[j] line lighting up. When j runs off the left edge or meets an element that is not bigger, the key drops into the open slot. By the time i reaches the end, the whole array is green.
The code, line by line
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a- The outer loop starts at
i = 1: the first element is a sorted list of length one, so there is nothing to do for it. key = a[i]lifts the current element out. We now have a "hole" we can shift things into.- The while loop walks
jbackward through the sorted prefix. As long asa[j]is bigger than the key, it does not belong before the key — so we copy it one slot right witha[j + 1] = a[j]and stepjleft. - When the loop stops (we ran off the front, or found something
<= key),a[j + 1] = keydrops the key into the gap. Because we shift rather than swap, the key only gets written once.
Complexity
| Case | Time | Notes |
|---|---|---|
| Best | O(n) (moderate) | already sorted — the while loop never runs |
| Average | O(n²) (slow) | |
| Worst | O(n²) (slow) | reverse-sorted — every key shifts past the whole prefix |
O(1) (fast)Insertion sort is adaptive: on a nearly-sorted array each key only moves a little, so it approaches O(n). That best case is its superpower — the other simple sorts cannot do it.
Selection sort: the sibling
Selection sort attacks from the other side. Instead of inserting each element where it belongs, it repeatedly finds the minimum of the unsorted suffix and swaps it to the front.
def selection_sort(a):
for i in range(len(a)):
min_i = i
for j in range(i + 1, len(a)):
if a[j] < a[min_i]:
min_i = j
a[i], a[min_i] = a[min_i], a[i]
return aFor each position i, scan the rest of the array to find the smallest value, then swap it into place. After i rounds, the first i slots hold the i smallest values in order.
How they compare:
| Insertion sort | Selection sort | |
|---|---|---|
| Time (all cases) | O(n²) worst/avg, O(n) best | O(n²) always — even if sorted |
| Swaps / writes | many shifts | at most n − 1 swaps |
| Adaptive? | yes — fast on nearly-sorted data | no — same work regardless of input |
| Stable? | yes | no (the long-distance swap can reorder equal keys) |
The headline: both are O(n²), so neither scales. But insertion sort is adaptive and stable, while selection sort minimizes the number of swaps — handy when a write is far more expensive than a comparison.
When to use / pitfalls
Reach for insertion sort when the input is small or nearly sorted — it is so cheap on those that real-world sorts (like Timsort, Python's built-in) use it for tiny sub-arrays. Mention that it is stable and adaptive to show you know why it survives inside industrial sorts. Pick selection sort only when writes are the bottleneck (e.g. flash memory), since it does the fewest swaps.
Off-by-one traps live in the insertion step. The key lands at a[j + 1], not a[j], because the while
loop decrements j one step past the correct slot before exiting. And the loop condition must check
j >= 0 before a[j] > key, or a key that belongs at the very front reads a[-1] and breaks.
Practice
Insertion-sorting [5, 2, 4, 1], when i reaches the last element (key = 1), how many elements get shifted right before the key is dropped in?
1. What does insertion sort do with the element at index i (the key)?
2. Why can insertion sort hit O(n) in the best case while selection sort cannot?
3. What is selection sort optimal at compared with insertion sort?
4. In a[j + 1] = key, why j + 1 and not j?