Overview
Insertion Sort builds a sorted prefix, inserting each new element into its correct spot within that prefix.
Analogy
Sorting a hand of cards: slide the new card left until it fits.
Step-by-step
- Treat the first element as sorted.
- For i from 1..n-1, set key = arr[i].
- Shift larger prefix elements right until key fits.
- Place key at j+1 where the gap opened.
- Repeat until all elements are inserted.
Visual
[5 | 2 4 6 1] → insert 2 → [2 5 | 4 6 1] → insert 4 → [2 4 5 | 6 1] …
Common mistakes
- Swapping instead of shifting (extra writes).
- Forgetting to store key before shifting, losing the value.
- Loop bounds that let j go -1 without handling the stop.
Practice questions
- Simulate on nearly sorted input and count comparisons.
- Explain why insertion sort is stable.
- Sort descending and confirm complexity stays the same.
Time
O(n²) worst, O(n) best on sorted input
AI Wisdom