Insertion Sort Visualization & Animation
Builds a sorted array one element at a time by inserting each into its correct position; O(n) on nearly-sorted input.
## What is it?
Insertion Sort builds a sorted array one element at a time. It picks each element from the unsorted region and inserts it into its correct position in the sorted region — just like sorting playing cards in your hand.
## How it works
- Treat the first element as a sorted array of size 1
- Pick the next element (`key`) from the unsorted portion
- Compare `key` with each element in the sorted portion from right to left
- Shift elements that are greater than `key` one position to the right
- Insert `key` in the correct gap
- Repeat until all elements are in the sorted portion
## When to use
- Small arrays (n < 20) where it outperforms O(n log n) algorithms in practice
- Nearly sorted arrays — performs O(n) in the best case
- Online sorting — new elements can be inserted without re-sorting from scratch
## Key Points
- Stable sort — preserves relative order of equal elements
- In-place — O(1) extra space
- Best case O(n) when input is already sorted
- Adaptive — performs better on partially sorted data
Category: algorithms
Difficulty: beginner
Time Complexity: O(n²) avg, O(n) best
Space Complexity: O(1)
View Insertion Sort Visualization