Foundations · Beginner
Insertion Sort
Grow a sorted prefix by inserting each new item into the gap where it belongs.
- Best
- O(n)
- Average
- O(n²)
- Worst
- O(n²)
- Space
- O(1)
- Stability
- Stable
- Memory model
- In-place
How it builds order
- Lift the next key from the unsorted suffix.
- Shift larger prefix values one slot right.
- Drop the key into the gap.
- Repeat until the prefix covers the list.
Why it works
Before each insertion the prefix is sorted; shifting preserves that order and opens exactly the key’s position.
Watch for: Everything left of the boundary stays sorted while larger values shift right.
The interactive version of this page adds the full trace, synchronized pseudocode, practice decisions, input experiments, and mastery review.