Incremental Algorithms
Grow the sorted prefix by one element at a time, repairing the order as each arrives.
Insertion Sort: Seven values
1 is the smallest so far and sits at index 0. Prefix sorted through index 1.
Cost
- Space
- O(1)
Before this
Related
Taught by the same lesson
Insertion Sort covers these too, in the same run.