CodeWithYash

Foundation · Module 4 · Lesson 3

Insertion Sort

Insert each value into an already sorted prefix.

15–25 min readLesson 21 of 123 Interactive Lab
Jump to interactive visualizer

Lesson 21 of 123

1d streak

Interactive Visualization

Trace the algorithm state by state

Change the inputs, run an operation, and connect each visible state change to the explanation below.

Step-through visualizer

Insertion Sort

Follow the state transition, then use the controls to test your prediction.

Blue: Key element being insertedOrange: Under comparison / shiftingGreen: In Sorted Prefix
15
0
6
1
22
2
9
3
3
4
18
5
startIndex 0 is trivially a sorted prefix of length 1.
Step 1 / 20

Theory lesson · Step-by-step

Understand Insertion Sort

Insert each value into an already sorted prefix.

Worked approach

Trace the reasoning step by step

  1. 1Treat the first value as a sorted prefix.
  2. 2Save the next key.
  3. 3Shift larger prefix values one position right.
  4. 4Insert the key into the opened position.

Concrete example

Insert values of [3, 1, 2] into a sorted prefix.

  1. 1Insert 1 before 3 → [1,3,2].
  2. 2Shift 3 and insert 2 → [1,2,3].

The prefix is sorted after every insertion.

What must remain true (Loop Invariant)

Before each iteration, the prefix [0, i) is sorted.

Cost Model

Complexity & Trade-offs

Sort
O(n²), best O(n)
O(1)
Include stability and input shape when comparing sorts.

When to use it

  • Creating order before searching, grouping, deduplicating, or scanning.
  • Selecting records using stability, memory, and input-shape constraints.
  • Turning pairwise decisions into monotonic scans.

Common mistakes

  • Comparing time alone while ignoring stability and auxiliary memory.
  • Breaking duplicate order when stability is required.
  • Quoting average performance without worst-case behavior.

Practice prompts

  • Reproduce the worked Insertion Sort example without looking at the trace.
  • Change one input condition and explain whether the Insertion Sort invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.