Insertion Sort
Take the next value and slide it left past larger values into the sorted prefix.
Insertion Sort: Seven values
5 is larger than 1, so 1 slides left.
Cost
- Best
- O(n)
- Average
- O(n^2)
- Worst
- O(n^2)
- Space
- O(1)
Fast on nearly sorted input. The standard choice for tiny arrays.
Properties
- Yes: Comparison based
- Yes: Stable
- Yes: In place
- Yes: Adaptive
- Yes: Online
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Insertion Sort covers these too, in the same run.