ƒ(x) SortingCore interactive
Insertion Sort
Build a sorted region one card at a time.
insertion_sort
step 1 / 34
44
8
18
20
88
94
64
34
50
94
94
First element is a sorted region of one.
comparingmovingsorted
speed1×
How it works
Insertion sort grows a sorted prefix by taking each new element and sliding it left into position — exactly how you sort a hand of cards. It's O(n²) worst case but blazing on nearly-sorted or small inputs, which is why hybrids fall back to it.
Mental models
- Adaptive: the closer to sorted, the faster it runs.
- Stable and in-place — production sorts use it for small subarrays.
Complexity
- Best
- O(n)nearly sorted
- Average
- O(n²)
- Worst
- O(n²)
- Space
- O(1)