Step-by-Step Process

Let’s trace through insertion sort with a concrete example: [5, 2, 8, 1, 9].

Visual Walkthrough

Interactive Diagram

This interactive diagram requires JavaScript to be enabled.

Steps:

1. Start: First element (5) is sorted. Current element is 2.
2. Insert 2: Compare with 5, shift 5 right, insert 2 at position 0.
3. Continue: Process 8 (already in place), then 1 (needs shifting), then 9.

Detailed Example

Sorting [5, 2, 8, 1, 9]:

Pass 1: Element = 2

• Compare 2 with 5: 2 < 5, shift 5 right
• Insert 2 at position 0
• Result: [2, 5, 8, 1, 9]

Pass 2: Element = 8

• Compare 8 with 5: 8 > 5, no shift needed
• Insert 8 at position 2
• Result: [2, 5, 8, 1, 9]

Pass 3: Element = 1

• Compare 1 with 8: 1 < 8, shift 8 right
• Compare 1 with 5: 1 < 5, shift 5 right
• Compare 1 with 2: 1 < 2, shift 2 right
• Insert 1 at position 0
• Result: [1, 2, 5, 8, 9]

Pass 4: Element = 9

• Compare 9 with 8: 9 > 8, no shift needed
• Insert 9 at position 4
• Result: [1, 2, 5, 8, 9] ✓

Interactive Visualization

Key Observations

1. Sorted portion grows: Left side is always sorted
2. One element at a time: Process one unsorted element per pass
3. Shifting: Larger elements shift right to make room
4. Insertion: Place current element in correct position

What’s Next?

Now that you’ve seen the process, let’s understand the algorithm in detail.