AlgoScope

Incremental Algorithms

Grow the sorted prefix by one element at a time, repairing the order as each arrives.

Algorithmic paradigms, paradigm, intermediate
1 inserted at index 0. Indices 0 to 1 are now sorted.sorted 0-110514223843576ji
1 inserted at index 0. Indices 0 to 1 are now sorted.sorted 0-110514223843576ji

Insertion Sort: Seven values

Step, step 4 of 27

1 is the smallest so far and sits at index 0. Prefix sorted through index 1.

Cost

Space
O(1)

Taught by the same lesson

Insertion Sort covers these too, in the same run.